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
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
|
<html dir="ltr" class="TridactylThemeDark" lang="en"><head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Computer Science 372: Design and Analysis of Algorithms</title>
<link href="index_files/custom_styles.css" media="screen" rel="stylesheet" type="text/css">
<link type="text/css" rel="stylesheet" href="index_files/course_specific_styles.html">
<script src="index_files/moodle_links.js" type="text/javascript" language="JavaScript"></script>
<style type="text/css">@media print {
.TridactylStatusIndicator {
display: none !important;
}
}</style></head><iframe class="cleanslate hidden" src="index_files/commandline.html" id="cmdline_iframe" loading="lazy" style="height: 0px !important;"></iframe>
<body>
<div class="au-course-interface">
<a id="top" name="top"></a>
<p class="runhead1">Computer Science 372: Design and Analysis of Algorithms</p>
<p> </p>
<hr>
<h2> Table of Contents </h2>
<ul>
<li><a href="#unit_00">Unit 0: Orientation</a>
<ul>
<li><a href="#unit_00_section_01">Course Outline</a></li>
<li><a href="#unit_00_section_01a">Learning Outcomes</a></li>
<li><a href="#unit_00_section_02">Discussion Forum</a></li>
<li><a href="#unit_00_section_03">Issues in Algorithm Design</a></li>
<li><a href="#unit_00_section_04">What I Expect of You</a></li>
<li><a href="#unit_00_section_05">What You Can Expect of Your Coordinator and Your Tutor</a></li>
<li><a href="#unit_00_section_06">Learning Happens in This Course—You Are in Control</a></li>
<li><a href="#unit_00_section_07">Textbook</a></li>
<li><a href="#unit_00_section_08">Useful Links</a></li>
<li><a href="#unit_00_section_09">Assessment</a></li>
<li><a href="#unit_00_section_10">Plagiarism</a></li>
</ul></li>
<li><a href="#unit_01">Unit 1: Foundations</a>
<ul>
<li><a href="#unit_01_section_01">Section 1.1: Problems</a></li>
<li><a href="#unit_01_section_02">Section 1.2: Complexity and Analysis</a></li>
<li><a href="#unit_01_section_03">Section 1.3: Asymptotics</a></li>
</ul></li>
<li><a href="#unit_02">Unit 2: Divide-and-Conquer Algorithms</a>
<ul>
<li><a href="#unit_02_section_01">Section 2.1: The Maximum-subarray Problem</a></li>
<li><a href="#unit_02_section_02">Section 2.2: Strassen’s Algorithm for Matrix Multiplication</a></li>
<li><a href="#unit_02_section_03">Section 2.3: Methods for Solving Recurrences</a></li>
</ul></li>
<li><a href="#unit_03">Unit 3: Dynamic Programming and Longest Common Subsequence</a>
<ul>
<li><a href="#unit_03_section_01">Section 3.1: Dynamic Programming</a></li>
<li><a href="#unit_03_section_02">Section 3.2: Longest Common Subsequence</a></li>
</ul></li>
<li><a href="#unit_04">Unit 4: Greedy Algorithms</a>
<ul>
<li><a href="#unit_04_section_01">Section 4.1: Greedy Algorithms</a></li>
</ul></li>
<li><a href="#unit_05">Unit 5: Multithreaded Algorithms</a>
<ul>
<li><a href="#unit_05_section_01">Section 5.1: Dynamic Multithreading Model</a></li>
<li><a href="#unit_05_section_02">Section 5.2: Matrices Multiplication with Multithreading</a></li>
</ul></li>
<li><a href="#unit_06">Unit 6: Number-Theoretic Algorithms</a>
<ul>
<li><a href="#unit_06_section_01">Section 6.1: Concepts of Number Theory</a></li>
<li><a href="#unit_06_section_02">Section 6.2: Euclid’s Algorithm</a></li>
<li><a href="#unit_06_section_03">Section 6.3: Modular Algorithms</a></li>
<li><a href="#unit_06_section_04">Section 6.4: Chinese Remainder Theorem and Powers of an Element</a></li>
<li><a href="#unit_06_section_05">Section 6.5: RSA Public-key Cryptosystem</a></li>
</ul></li>
<li><a href="#unit_07">Unit 7: NP-completeness</a><ul>
<li><a href="#unit_07_section_01">Section 7.1: P ≠ NP Question</a></li>
<li><a href="#unit_07_section_02">Section 7.2: NP-completeness</a></li>
</ul></li>
<li><a href="#unit_08">Unit 8: Approximation Algorithms</a>
<ul>
<li><a href="#unit_08_section_01">Section 8.1: Performance Ratios</a></li>
<li><a href="#unit_08_section_02">Section 8.2: The Vertex-cover Problem</a></li>
<li><a href="#unit_08_section_03">Section 8.3: The Set-covering Problem</a></li>
<li><a href="#unit_08_section_04">Section 8.4: The Subset-sum Problem</a></li>
</ul></li>
</ul>
<hr>
<a name="unit_00"></a><h2>Unit 0: Orientation</h2><p>Please let me
explain some essential information that you will need to meet the
course outcomes and successfully complete this course. I will discuss
expectations, both those that you should have of your tutor and me, and
those that I have of you. This course takes place in the Moodle course
site where you are now. Here you will find the following:</p>
<ul>
<li>the units of the study guide</li>
<li>the COMP 372 General Discussion Forum where students and
instructors share general information about course procedures and
materials, and where you post your answers to assigned questions as
part of the participation mark</li>
<li>The Assignments section where you submit completed work and check for marker evaluation and feedback</li>
<li>The Help and Resources section with links to pages that support you as a learner at AU</li>
</ul><br>
<div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_01"></a><h2>Course Outline</h2>
<p>The course consists of the following nine units.</p>
<p>Unit 0 - Orientation</p>
<p>Unit 1 - Foundations</p>
<ul><li>Problems</li><li>Complexity</li><li>Analysis</li><li>Asymptotic notation</li></ul>
<p>Unit 2 - Divide-and-Conquer Algorithms</p>
<ul><li>The maximum-subarray problem</li><li>Strassen’s algorithm for matrix multiplication</li><li>Methods for solving recurrences</li></ul>
<p>Unit 3 - Dynamic Programming and Longest Common Subsequence</p>
<ul><li>Rod cutting</li><li>Matrix-chain multiplication</li><li>Elements of dynamic programming</li><li>Longest common subsequence</li></ul>
<p>Unit 4 - Greedy Algorithms</p>
<ul><li>Greedy approach</li><li>Data-compression (Huffman) codes</li></ul>
<p>Unit 5 - Multithreaded Algorithms</p>
<ul><li>Dynamic multithreading model</li><li>Metrics of work, span, and parallelism</li><li>Matrices multiplication with multithreading</li></ul>
<p>Unit 6 - Number-theoretic Algorithms and RSA Cryptosystem</p>
<ul><li>Basic concepts</li><li>Euclid’s algorithm</li><li>Modular algorithm</li><li>Repeated-squaring algorithm</li><li>RSA public-key cryptosystem</li></ul>
<p>Unit 7 - NP-completeness</p>
<ul><li>NP question</li><li>NP-completeness</li></ul>
<p>Unit 8 - Approximation Algorithms</p>
<ul><li>Performance ratio</li><li>The vertex-cover problem</li><li>The set-covering problem</li><li>The subset-sum problem</li></ul>
<div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_01a"></a><h2>Learning Outcomes</h2>
<p>Upon successful completion of this course, you should be able to</p>
<ul>
<li>describe the major modern algorithms and selected techniques that are essential to today’s computers.</li>
<li>identify the key characteristics of a given problem and analyze the
suitability of a specific algorithm design technique for the problem.</li>
<li>apply the algorithms and design techniques to solve problems, and
mathematically evaluate the quality of the solutions, typically using
the following algorithms:
<ul class="circle">
<li>dynamic programming</li>
<li>greedy</li>
<li>multithreaded</li>
<li>number-theoretic</li>
<li>approximation</li>
</ul></li>
<li>analyze NP-complete problems and develop algorithms to solve the problems.</li>
<li>implement a solution for a given problem and algorithm in high-level programming languages.</li>
</ul>
<div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_02"></a><h2>Discussion Forum</h2><p>As
a student in this course you are expected to participate in the forum
discussions and ensure that you are notified of discussion posts. You
should <em>remain subscribed</em> to the COMP 372 General Discussion Forum.</p>
<p> </p><br>
<div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_03"></a><h2>Issues in Algorithm Design</h2><p>Algorithms
are mathematical objects (in contrast to the much more concrete notion
of a computer program implemented in some programming language and
executed on some machine). Thus we can reason about the properties of
algorithms mathematically. </p>
<p>When designing an algorithm there are two fundamental issues to be considered: <strong><em>correctness</em></strong> and <strong><em>efficiency</em></strong>.
It is important to justify an algorithm’s correctness mathematically.
For very complex algorithms, this typically requires a careful
mathematical proof, which may require the proof of many lemmas and
properties of the solution upon which the algorithm relies. </p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_04"></a><h2>What I Expect of You</h2><p>COMP
372 is a senior-level course in an undergraduate program offered by
Athabasca University. I have high expectations of you. You should be
curious and willing to seek out information besides the provided
textbook and learning materials. You should be willing to discuss what
you discover in the COMP 372 discussion forum with the tutor and with
other students. You should also be willing to ask questions in the
forum or email your tutor at any time. If you see a question on a
discussion forum and you know the answer, you should post a reply.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_05"></a><h2>What You Can Expect of Your Coordinator and Your Tutor</h2><p>Your
tutor is a professional who enjoys the learning experience. Your tutor
wants to see you succeed and is willing to be a partner in that
success. Questions regarding the learning material should be posted to
the COMP 372 General Discussion Forum, where other students, your
tutor, or the course coordinator may reply. Personal questions should be
directed to your tutor or the course coordinator.</p>
<p>There are <a href="http://www2.athabascau.ca/students/servicestandards.php">policies and service standards</a> that specify how you may contact us and how soon you should expect a reply. We take those standards seriously.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_06"></a><h2>Learning Happens in This Course—You Are in Control</h2><p>This course is like other undergraduate courses at Athabasca University in that it is <em>unpaced</em>.
This means that you have registered for a 6-month contract. During
those 6 months, you are in total control. The study guide presents a
list of readings and activities that you must perform to successfully
complete this course. The course site is laid out in a suggested
16-week progression, but you control your own schedule.</p>
<p>The readings follow the textbook for this course, and all other
materials are available on the Web. The Web is full of thousands of
pages of helpful algorithm material including video lectures, slides,
and source code. Please visit the <em>Coordinator’s </em><a href="http://oscar.athabascau.ca/COMP372/index.html">COMP372 web page</a> from time to time.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_07"></a><h2>Textbook</h2><p class="reference">Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). <em><a href="http://mitpress.mit.edu/books/introduction-algorithms">Introduction to Algorithms</a></em> (3rd ed.). MIT Press. </p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_08"></a><h2>Useful Links</h2><p>We
strongly encourage sharing and welcome intelligent (and properly
acknowledged) reuse of ideas, content, and systems, but as for any
course at Athabasca University, we very strongly frown upon plagiarism,
collusion, and other forms of academic misconduct; in the unlikely
event that you feel tempted to do so, we will come down on you like a
pile of very sharp bricks. </p>
<p>If you use the work of others, whether explicitly using the same content or basing your ideas on theirs, you <em>must</em> properly list and cite your sources in <em>all</em>
cases. It is better to do too much than too little. Failure to
properly cite sources may lead to anything from censure and loss of
marks in very minor cases of forgetfulness (e.g., if you provide
reference to a source in your bibliography list but do not cite at the
point at which you use it), to expulsion from the course and a
permanent stain on your academic record if uncited work is used. We
have access to automated and semi-automated tools for plagiarism
detection and may use them. </p>
<p>The good news is that there is plenty of information online to help avoid this happening, including our own <a href="http://write-site.athabascau.ca/">Write Site</a>,
which offers great advice on the subject, and in our own school and
faculty policies. We know that in by far the majority of cases, people
who are guilty of academic misconduct are simply unaware of what is
correct and how to avoid the pitfalls. If you have not already done so,
please visit the Write Site or explore other online sources explaining
plagiarism, collusion, and other forms of academic misconduct, and
remember that by signing on to one of our courses, you have explicitly
agreed that you will behave with total academic honesty throughout.</p>
<h3>What if you spot academic misconduct from others?</h3>
<p>First of all, tell <em>them</em> about it! In most cases, academic
misconduct is unintentional and, if you let people know that you have
identified a problem, they will nearly always try to fix it.</p>
<p>If they don't fix it, tell us! If you suspect a fellow student of
academic misconduct, then it is important to inform us of your
suspicions, because there is a slight chance that we may not recognize
it ourselves, and the reputation of the course (and hence of your own
qualification) depends on the course maintaining high standards of
reliability and trustworthiness. This is not snitching: it is for your
own benefit and for the benefit of everyone on the course to ensure
that the highest standards are maintained. Cheating benefits no one:
the person cheating fails to learn, and your qualification loses value
as a result.</p>
<h3>Citation Practice</h3>
<p>It is vitally important that when you make use of the work of
someone else, that you cite it correctly. Your learning journal for
each unit must contain a <strong>References</strong> section that lists all the sources you need to cite in your journal.</p>
<p>For non-web sources such as books, journal articles, and conference
papers, we recommend that you use the APA standard for citation.
Information about this can be found at the <a href="http://write-site.athabascau.ca/">Write Site.</a> </p>
<p>For web-based sources, it is good practice to provide a live
hyperlink to the actual page that you are citing—Snot just the site on
which it can be found. You should also make a note of the date when the
page was accessed.</p>
<h3>Using (not abusing) <em>Wikipedia</em></h3>
<p>This course makes extensive use of <em>Wikipedia</em> articles as learning resources to help frame ideas and discussions. We do this because <em>Wikipedia</em>
provides quick and digestible overviews of many topics that are
discussed here. Rather than paraphrase such overviews, some of which
you may already know or that may be irrelevant to your needs, we think
it is more sensible to send you to a source that has been edited by
many individuals and is therefore likely to be reasonably clear and
reliable. </p>
<p>However, you should never rely solely on <em>Wikipedia</em> as an
information source. We like it because it is a great way to get the
general gist of many topics, but it is not always 100% reliable and,
more significantly, it does not go into any significant depth on
anything. It also has a tendency to gloss over big intellectual debates
and differences, almost never has anything new to say on academic
issues, and sometimes misses important and relevant issues. Where we
think you would gain a lot from exploring further, we provide links to
other sources, often to academic papers. However, we strongly encourage
you to explore further links and references yourself. You might find
these within <em>Wikipedia</em> articles, or you might search for topics that suggest themselves in <em>Wikipedia</em> in more diverse places, especially scholarly articles such as can usually be found through Google Scholar (<a href="http://scholar.google.com/">http://scholar.google.com</a>) or Microsoft's rather less well developed Academic Search (<a href="http://academic.research.microsoft.com/">http://academic.research.microsoft.com</a>). Remember the mantra—"<em>Wikipedia</em> is a great place to start and a terrible place to finish."</p>
<p>Please note that <em>Wikipedia</em> is a great learning tool and
can be very useful as a starting point for research, but it is not a
good source to cite. This is not a properly peer-reviewed source,
provides too little detail, and it cannot be called upon to provide
reliable evidence to back up your own arguments and discussions. In your
own work, please do not use <em>Wikipedia</em> articles as referenced
resources. Indeed, you should avoid citing any encyclopaedia or
dictionary at all, for much the same reasons. This includes <em>Encyclopaedia Britannica</em>. </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_09"></a><h2>Assessment</h2><h3>Assignments</h3>
<p>You are required to save your answers to the exercises in Microsoft
Word, plain text, or PDF files. When you complete all the exercises of
an assignment, you are required to zip them into a single file and
submit it via the assignment link on the course home page. </p><p>The five assignments are worth 70% of the final grade: </p>
<p><strong>Assignment 1: Problem Set 1</strong> – Submit all your solutions to the selected exercises in Chapters 1, 2, 3 and 4 of the textbook after completing Unit 2. </p>
<p><strong>Assignment 2: Problem Set 2</strong> – Submit all your solutions to the selected exercises in Chapters 15 and 16 of the textbook after completing Unit 4. </p>
<p><strong>Assignment 3: Problem Set 3</strong> – Submit all your solutions to the selected exercises in Chapters 27 and 31 of the textbook after completing Unit 6.</p>
<p><strong>Assignment 4: Problem Set 4</strong> – Submit all your solutions to the selected exercises in Chapters 34 and 35 of the textbook after completing Unit 8.</p>
<p><strong>Assignment 5: Project</strong> – You should submit the project before writing the final exam. </p>
<h4>Doing the Assignments</h4>
<p>Throughout this course, when you are asked to present an algorithm, this means that you need to do three things: </p>
<ol>
<li>Present a clear, simple, and unambiguous description of the algorithm (in pseudocode, for example). The key here is <em>keeping it simple</em>.
Uninteresting details should be kept to a minimum, so that the key
computational issues stand out. For example, it is not necessary to
declare variables whose purpose is obvious, and it is often simpler and
clearer to simply say, “Add <em>X </em>to the end of list <em>L</em>” than to present code to do this or use some arcane syntax, such as “<em>L:insertAtEnd</em>(<em>X</em>).”</li>
<li>Present a justification or proof of the algorithm’s correctness.
Your justification should assume that the reader is someone of similar
background to yours, say another student in this class, and should be
convincing enough make a skeptic believe that your algorithm does
indeed solve the problem correctly. Avoid rambling about obvious or
trivial elements. A good proof provides an overview of what the
algorithm does and then focuses on any tricky elements that may not be
obvious. </li>
<li>Present a worst-case analysis of the algorithm's efficiency,
typically its running time (but also its space, if space is an issue).
Sometimes this is straightforward, but if not, concentrate on the parts
of the analysis that are not obvious. </li>
</ol>
<h3>Participation</h3>
<p>You can earn up to 5% of your final grade through participation
marks. To do so, post to the COMP 372 on a regular basis. Answer the
questions from the study guide, and comment on answers and respond to
questions from other students. At the end of the course, you will submit
a summary of your participation activities to the Participation link
under Assessments on the course home page.</p>
<h3>Final Examination</h3>
<p>The final invigilated examination is worth 25% of your grade. It is
a closed-book examination to be completed online without any printed
material or electronic devices outside of the online invigilation system
(e.g., notes, tapes, cell phone, smartwatch, tablet, etc.). You may NOT
use your textbooks or consult with other people while writing this
examination. A maximum of three hours is allowed to complete the
examination.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_00_section_10"></a><h2>Plagiarism</h2><p>From the Athabasca University document on Academic Integrity:</p>
<p>“Students registered in Athabasca University courses are
considered to be responsible scholars and are therefore expected to
conform to the highest standards of academic integrity in all written
assignments, including examinations.”</p>
<p>I also refer everyone to the Student Code of Conduct, specifically Academic Misconduct:</p>
<p><a href="http://calendar.athabascau.ca/undergrad/current/page11.php#acad_misconduct">http://calendar.athabascau.ca/undergrad/current/page11.php#acad_misconduct</a></p>
<p>Specifically, you cannot copy text from a source and present it as your own words<strong>.</strong> </p>
<p>Any quoted text should be displayed as a quotation (as I did in
the first paragraph above) with a clear citation of the source. You
also need to cite sources that you paraphrase, i.e., rephrase in your
own words. Sources you cite must also be listed as a reference.
See <a href="http://owl.english.purdue.edu/owl/resource/560/01/">http://owl.english.purdue.edu/owl/resource/560/01/</a> for examples of how to list and cite sources using APA style, which is acceptable for COMP 372.</p>
<h3>Penalties</h3>
<p><a href="http://calendar.athabascau.ca/undergrad/page11_03_new.php">http://calendar.athabascau.ca/undergrad/page11_03_new.php</a></p>
<p>Specifically, the first penalty is a reduction in grade (item 'c'
in the above web document). If the misconduct is repeated, further
penalties are, up to and including, a failing grade in the course (d),
suspension (e) or expulsion (f) from Athabasca University.<strong> </strong>All instances of plagiarism will be reported to the Dean of Faculty of Science and Technology. </p>
<p>Be certain the words you submit as your own words are indeed your
own words. You can paraphrase and quote (with proper attribution),
but you cannot copy other people’s words and present them as your own.</p>
<p><strong>Warning:</strong> Plagiarism detection software may be used on submitted assignments to insure compliance. </p>
<p>Finally, here is a tutorial on plagiarism developed at University
of Maryland. It is very useful introduction to all aspects of citation,
plagiarism, policies, etc. Please have a look at it:</p>
<p><a href="https://www.umgc.edu/current-students/learning-resources/academic-integrity/tutorial/index.cfm">https://www.umgc.edu/current-students/learning-resources/academic-integrity/tutorial/index.cfm</a></p>
<p>If you have any questions about plagiarism, please post them on the COMP 372 General Discussion Forum for discussion. </p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_01"></a><h2>Unit 1: Foundations</h2><p>First,
I assume that you know overall the importance of algorithms and what
an algorithm is. But from this unit I hope you will gain a better
understanding of what kinds of problems are solved by algorithms. Also
you will become familiar with the framework we will use throughout the
course to think about the design and analysis of algorithms. </p>
<p>This unit addresses the following topics of interest:</p>
<ul>
<li>an overview of algorithms and their place in modern computing systems<strong> </strong></li>
<li>a thorough examination of two different sorting algorithms (<em>insertion</em> sort and <em>merge</em> sort) to determine their running times and develop a useful notation to express them<strong> </strong></li>
<li>a definition of the notation (called <em>asymptotic notation</em>) that we use for bounding algorithm running times from above and/or below.</li>
</ul>
<p>Why do we choose asymptotic notation and analysis for algorithm
analysis? This approach allows us to focus on the “big-picture” aspects
of an algorithm’s running time.</p>
<p>The unit has three sections.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_01_section_01"></a><h2>Section 1.1: Problems</h2><p>Your goals for this section are </p>
<ul>
<li>to know the definition of algorithm, the reasons for studying
algorithms, and the role of algorithms relative to other technologies
used in computers.</li>
<li>to know what kind of problems are solved by algorithms.</li>
</ul>
<h3>Learning Objective 1.1.1 – Understanding Algorithms</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>give a definition of the term <em>algorithm</em>.</li>
<li>identify practical applications of algorithms.</li>
<li>explain the role of algorithms in computing science.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Watch the video, <a href="https://www.youtube.com/watch?app=desktop&v=HtSuA80QTyo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb">Algorithmic Thinking, Peak Finding</a>, on YouTube.</li>
<li>Study Chapter 1 of the textbook.</li>
<li>Study Chapter 1 of the textbook.</li>
<li>Do Exercises 1.1-4 and 1.2-2 from the textbook as part of Assignment 1. </li>
</ul>
<h4>Discussion Question</h4>
<p>Review Problem 1-1 on pages 14–15 of the textbook. How would you
go about solving this problem? Post a response, and comment on other
students' responses to earn participation marks and develop your skills
as an online communicator in the profession.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_01_section_02"></a><h2>Section 1.2: Complexity and Analysis</h2><p>Your goal for this section is to familiarize yourself with the framework that we will use throughout the course.</p>
<h3>Learning Objective 1.2.1 – Using Pseudocode</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>specify algorithms using <em>pseudocode</em>, that is, using the set of pseudocode conventions introduced in the textbook.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 4.1 of the textbook.</li>
<li>Study Section 2.1 of the textbook.</li>
<li>Do Exercise 2.1-3 from the textbook as part of Assignment 1. </li>
</ul>
<h3>Learning Objective 1.2.2 – Analyzing Algorithms</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>analyze the running time of algorithms. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 2.2 of the textbook.</li>
<li>Do Exercise 2.2-3 from the textbook as part of Assignment 1.</li>
</ul>
<p>For supplemental material, I recommend that you watch this video
(please ignore the beginning of the video talking about their course
information. You can start from 17:20): <a href="http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/1">http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/1</a></p>
<h3>Learning Objective 1.2.3 – Designing Algorithms</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>explain the divide-and-conquer approach to the design of algorithms. </li>
<li>use it to develop a merge sort algorithm.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 2.3 of the textbook.</li>
<li>Do Exercise 2.3-5 from the textbook as part of Assignment 1.</li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_01_section_03"></a><h2>Section 1.3: Asymptotics</h2><p>Your goals for this section are </p>
<ul>
<li>to know the meaning of the asymptotic efficiency of algorithms.</li>
<li>to define several types of asymptotic notation.</li>
<li>to use standard methods for simplifying the asymptotic analysis of algorithms.</li>
</ul>
<h3>Learning Objective 1.3.1 – Asymptotic Notation</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>define several types of asymptotic notation.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 3.1 of the textbook.</li>
<li>Do Exercise 3.1-1 from the textbook as part of Assignment 1. </li>
</ul>
<p>For supplemental material, I recommend that you watch this video: <a href="http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/2">http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/2</a></p>
<h3>Learning Objective 1.3.2 – Standard Notation and Common Functions</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>review some standard mathematical functions and notations, and explore the relations among them. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 3.2 of the textbook.</li>
<li>Do Problem 3-1 from the textbook as part of Assignment 1.</li>
</ul>
<h4>Question to Ponder and Discuss</h4>
<p>What are the common abuses in the basic asymptotic notations? Post
your thoughts on this to the COMP 372 General Discussion Forum.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_02"></a><h2>Unit 2: Divide-and-Conquer Algorithms</h2><p>In
the last unit, you learned the concept of divide and conquer. This
unit delves further into the divide-and-conquer method. It provides
some examples of divide-and-conquer algorithms, including Strassen’s
surprising method for multiplying two square matrices. And then, we
will study methods for solving recurrences, which are useful for
describing the running times of recursive algorithms. One of them, the
“master method,” is particularly powerful. </p>
<p>For supplemental material, I recommend that you watch this video: <a href="http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/3">http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/3</a> </p>
<p>This unit will introduce </p>
<ul>
<li>more examples of divide-and-conquer algorithms.</li>
<li>methods for analyzing recursive algorithms.</li>
</ul>
<p>The unit has three sections.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_02_section_01"></a><h2>Section 2.1: The Maximum-subarray Problem</h2><p>Your goal for this section is to become familiar with the maximum-subarray problem and its divide-and-conquer algorithm.</p>
<h3>Learning Objective 2.1.1 – The Maximum-subarray Problem</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe the maximum-subarray problem, and design and analyze its divide-and-conquer algorithm. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Watch the video, <a href="https://www.youtube.com/watch?app=desktop&v=yBCzO0FpsVc">Algorithms Lecture 13: Maximum Sub-array Problem using Divide-and-Conquer</a>, on YouTube.</li>
<li>Study Section 4.1 of the textbook.</li>
<li>Do Exercise 4.1-2 from the textbook as part of Assignment 1. </li></ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_02_section_02"></a><h2>Section 2.2: Strassen’s Algorithm for Matrix Multiplication</h2><p>Your goal for this section is to become familiar with Strassen’s algorithm for matrix multiplication.</p>
<h3>Learning Objective 2.2.1 – Strassen’s Method</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe Strassen’s method for matrix multiplication, and design and analyze its divide-and-conquer algorithm. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Watch the video, <a href="https://www.youtube.com/watch?app=desktop&v=1AIvlizGo7Y">Strassen’s Matrix Multiplication by Divide and Conquer</a>, on YouTube.</li>
<li>Study Section 4.2 of the textbook.</li>
<li>Do Exercise 4.2-1 from the textbook as part of Assignment 1. </li></ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_02_section_03"></a><h2>Section 2.3: Methods for Solving Recurrences</h2><p>Your goal for this section is to become familiar with the methods for solving recurrences.</p>
<h3>Learning Objective 2.3.1 – The Substitution Method </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe the substitution method for solving recurrences. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Watch the video, <a href="https://freevideolectures.com/course/1941/introduction-to-algorithms/2">Lecture 2: Asymptotic Notation | Recurrences | Substitution, Master Method (the Substitution part)</a>, at Free Video Lectures.</li>
<li>Study Section 4.3 of the textbook.</li>
<li>Do Exercises 4.3-2 from the textbook as part of Assignment 1. </li></ul>
<h3>Learning Objective 2.3.2 – The Recursion-tree Method</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe the recursion-tree method for solving recurrences. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Watch the video, <a href="https://freevideolectures.com/course/1941/introduction-to-algorithms/2">Lecture 2: Asymptotic Notation | Recurrences | Substitution, Master Method (the Recursion part)</a>, at Free Video Lectures.</li>
<li>Study Section 4.4 of the textbook.</li>
<li>Do Exercise 4.4-7 from the textbook as part of Assignment 1. </li>
</ul>
<h3>Learning Objective 2.3.3 – The Master Method</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe the master method for solving recurrences. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Watch the video, <a href="https://freevideolectures.com/course/1941/introduction-to-algorithms/2">Lecture 2: Asymptotic Notation | Recurrences | Substitution, Master Method (the Master Method part)</a>, at Free Video Lectures.</li>
<li>Study Section 4.5 of the textbook.</li>
<li>Do Exercise 4.5-3 from the textbook as part of Assignment 1. </li>
</ul>
<h1>Assignment 1</h1>
<p>It’s time to submit the problem set for Assignment 1 on the course home page in Moodle.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_03"></a><h2>Unit 3: Dynamic Programming and Longest Common Subsequence</h2><p>Dynamic
programming, like the divide-and-conquer method, solves problems by
combining the solutions to sub-problems. Why do we call it <em>programming</em>? In fact, programming in this context refers to a <strong>tabular</strong> method, not to writing computer code. The term <em>dynamic programming</em>
was first coined by Richard Bellman in the 1950s, a time when
computing programming was an esoteric activity practiced by so few
people as to not even merit a name. Back then programming meant <strong>planning</strong>, and “dynamic programming” was conceived to optimally plan multistage processes. </p>
<p>Why do we need dynamic programming?</p>
<p>Divide-and-conquer algorithms partition the problem into disjoint
sub-problems, solve the sub-problems recursively, and then combine
their solutions to solve the original problem. In contrast, dynamic
programming applies when the sub-problems overlap—that is, when
sub-problems share sub-sub-problems. In this context, a
divide-and-conquer algorithm does more work than necessary and
efficient! </p>
<p>The basic idea behind dynamic programming is <em>eliminating overlapping recursive calls by using more memory to keep track of previous values.</em></p>
<p>I recommend that you to watch this video from <a href="http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/15">http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/15</a> </p>
<p>This unit will address the following topics of interest:</p>
<ul>
<li>developing a dynamic-programming algorithm.</li>
<li>applying dynamic programming to optimization problems.</li>
</ul>
<p>The unit has two sections.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_03_section_01"></a><h2>Section 3.1: Dynamic Programming</h2><p>Your
goal for this section is to become familiar with the method of dynamic
programming and how to use the dynamic programming method to solve some
optimization problems.</p>
<h3>Learning Objective 3.1.1 – Rod Cutting</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>examine the problem of cutting a rod into rods of smaller length in a way that maximizes their total value. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 15.1 of the textbook.</li>
<li>Do Exercises 15.1-1 and 15.1-5 from the textbook as part of Assignment 2. . </li></ul>
<h3>Learning Objective 3.1.2 – Matrix-chain Multiplication</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe another example of dynamic programming—how we can
multiply a chain of matrices while performing the fewest total scalar
multiplications. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 15.2 of the textbook.</li>
<li>Do Exercises 15.2-1 and 15.2-2 from the textbook as part of Assignment 2. </li>
</ul>
<h3>Learning Objective 3.1.3 – Elements of Dynamic Programming</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>discuss two key characteristics that a problem must have for dynamic programming. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 15.3 of the textbook.</li>
<li>Do Exercise 15.3-1 from the textbook as part of Assignment 2. </li>
</ul>
<h4>Discussion Questions</h4>
<p>Examine Exercise 15.3-6 in the textbook. Post a response, and
comment on other students' responses to earn participation marks and
develop your skills as an online communicator in the profession.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_03_section_02"></a><h2>Section 3.2: Longest Common Subsequence</h2><p>Your goal for this section is to learn how to find the longest common subsequence of two sequences via dynamic programming.</p>
<h3>Learning Objective 3.2.1 – Longest Common Subsequence </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>show how to find the longest common subsequence of two sequences via dynamic programming. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 15.4 of the textbook.</li>
<li>Do Exercises 15.4-1 and 15.4-2 from the textbook as part of Assignment 2. </li></ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_04"></a><h2>Unit 4: Greedy Algorithms</h2><p>Before
learning this unit, you should learn dynamic programming. Why do we
study greedy algorithm? For many optimization problems, using dynamic
programming to determine the best <em>choices is overkill. </em></p>
<p>Like dynamic-programming algorithms, greedy algorithms typically
apply to optimization problems in which we make a set of choices in
order to arrive at an optimal solution.</p>
<p>The idea of a greedy algorithm is to make each choice in a locally optimal manner. </p>
<p>A simple example is coin-changing: to minimize the number of
Canadian coins needed to make change for a given amount e.g. CAD$38, we
can repeatedly select the largest-denomination coin that is no larger
than the amount that remains. We have 38-20=18, 18-10=8, 8-5 = 3, 3-2
=1, 1-1 =0. So $38 is changed to $20 + $10 + $5 +$2 + $1.</p>
<p>A greedy algorithm approach provides an optimal solution for many such problems much more <em>quickly</em> than would a dynamic programming approach. However, is this approach effective? This unit will introduce <em>matroid theory</em>, which provides a mathematical basis that can help us to show that a greedy algorithm yields an optimal solution. </p>
<p>Is the greedy method powerful? Yes, it is quite powerful and works
well for a wide range of problems. More importantly, the greedy
algorithm approach is more straightforward than the dynamic programming
approach. </p>
<p>I recommend that you to watch this video: <br>
<a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-16-greedy-algorithms-minimum-spanning-trees/">http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-16-greedy-algorithms-minimum-spanning-trees/</a> </p>
<p>This unit addresses the following topics of interest:</p>
<ul>
<li>the basic elements of the greedy approach </li>
<li>an important application of greedy techniques: designing data-compression (Huffman) codes</li>
</ul>
<p>The unit has only one section.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_04_section_01"></a><h2>Section 4.1: Greedy Algorithms</h2><p>Your goal for this section is to become familiar with greedy algorithms and their applications.</p>
<h3>Learning Objective 4.1.1 – An Activity-selection Problem </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe a simple but nontrivial problem, the
activity-selection problem, for which a greedy algorithm efficiently
computes an optimal solution. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 16.1 of the textbook.</li>
<li>Do Exercise 16.1-2 from the textbook as part of Assignment 2. </li></ul>
<h3>Learning Objective 4.1.2 – Elements of the Greedy Strategy </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>discuss some of the general properties of greedy methods and
tell whether a greedy algorithm will solve a particular optimization
problem. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 16.2 of the textbook.</li>
<li>Do Exercise 16.2-2 from the textbook as part of Assignment 2.</li>
</ul>
<h4>Discussion Questions</h4>
<p>Examine Exercise 16.2-3 in the textbook. Post a response, and
comment on other students' responses to earn participation marks and
develop your skills as an online communicator in the profession. </p>
<h1>Assignment 2</h1>
<p>It’s time to submit the problem set for Assignment 2 on the course home page.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_05"></a><h2>Unit 5: Multithreaded Algorithms</h2><p>With
the advent of multicore technology, every new laptop and desktop
machine is now a shared-memory parallel computer. However, programming a
shared-memory parallel computer directly using static threads is
difficult and error-prone. This state of affairs has led to the creation
of concurrency platforms, which provide a layer of software that
coordinates, schedules, and manages the parallel-computing resources. </p>
<p>In this unit, we introduce a model for dynamic multithreading, which
is a simple extension of our serial programming model. This model
allows the programmer to specify only the logic parallelism within a
computation and the threads within the underlying concurrency platform
schedule, which load-balance the computation themselves. That is, it
allows programmers to specify parallelisms in applications without
worrying about communication protocols, load balancing, and other
vagaries of static-thread programming. </p>
<p>And then we look at how to <strong>design</strong> multithreaded
algorithms written for this model. We will see how the underlying
concurrency platform can schedule computations efficiently. We present
the metrics of work, span, and parallelism and use them to analyze
multithreaded algorithms. </p>
<p>This unit will</p>
<ul>
<li>introduce the basics of the model.</li>
<li>show how to quantify parallelism in terms of the measures of work and span.</li>
<li>investigate a multithreaded algorithm for matrix multiplication.</li>
</ul>
<p>The unit has two sections.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_05_section_01"></a><h2>Section 5.1: Dynamic Multithreading Model</h2><h3>Learning Objective 5.1.1 – The Basics of Dynamic Multithreading </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>explain the dynamic multithreading model.</li>
<li>use the metrics of work, span, and parallelism to analyze multithreaded algorithms.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Watch this video: <a href="http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/20">http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/20</a>, also available here: <a href="http://youtu.be/PYvJmLKhM-Y">http://youtu.be/PYvJmLKhM-Y</a></li>
<li>Study Section 27.1 of the textbook.</li>
<li>View tutorial slides from <a href="http://student.athabascau.ca/~oscarl/COMP372/MultithreadedAlgorithms%20Part%201.pptx">http://student.athabascau.ca/~oscarl/COMP372/MultithreadedAlgorithms Part 1.pptx</a></li>
<li>Complete the following exercises:
<ol>
<li>Explain these keywords or terms relating to parallel algorithms:
<ul>
<li>Spawn</li>
<li>Sync</li>
<li>Nest parallelism</li>
<li>Strand</li>
<li>Computation dag</li>
<li>Work</li>
<li>Span</li>
<li>Critical path</li>
<li>Parallelism</li>
<li>Parallel for</li>
</ul>
</li>
<li>Explain how a multithreaded scheduler works. </li>
</ol>
</li>
</ul>
<ul>
<li>Do Exercises 27.1-1 and 27.1-7 from the textbook as part of Assignment 3. </li>
</ul>
<h4>Questions to Ponder and Discuss</h4>
<ul>
<li>What do we need parallel algorithms?</li>
<li>What are the key features of the model for dynamic multithreading?</li>
<li>What are the important advantages of dynamic multithreading? </li>
</ul>
<p>Post your thoughts on this to the COMP 372 General Discussion Forum.</p>
<h4>Further Readings</h4>
<p>At the end of each chapter in the textbook, you will find a
section titled “Chapter notes.” While the references and readings
mentioned in this section are not assigned, please feel free to examine
them if you are interested, or ask questions on the COMP 372 General
Discussion Forum. </p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_05_section_02"></a><h2>Section 5.2: Matrices Multiplication with Multithreading</h2><h3>Learning Objective 5.2.1 – Matrices Multiplication with Multithreading </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>design and analyze multithreaded algorithms based on the
standard triply nested loop, as well as divide-and-conquer algorithms.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 27.2 of the textbook.</li>
<li>Do Exercise 27.2-1 from the textbook as part of Assignment 3. </li></ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_06"></a><h2>Unit 6: Number-Theoretic Algorithms</h2><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_06_section_01"></a><h2>Section 6.1: Concepts of Number Theory</h2><h3>Learning Objective 6.1.1 – Elementary Number-theoretic Notions</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>discuss elementary number-theoretic notions.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 31.1 of the textbook.</li>
<li>Explain the following elementary but important concepts:
<ul>
<li>Divisor</li>
<li>Prime number </li>
<li>Quotient, remainder, division theorem</li>
<li>Equivalence class modulo <em>n</em>, the set Zn</li>
<li>Common divisor, greatest common divisor</li>
<li>Relatively prime, pairwise relatively prime numbers</li>
<li>Unique factorization </li>
</ul>
</li>
<li>Do Exercise 31.1-7 from the textbook as part of Assignment 3. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_06_section_02"></a><h2>Section 6.2: Euclid’s Algorithm</h2><p>Your
goal in this section is to study and analyze one of the world’s oldest
algorithms: Euclid’s algorithm for computing the greatest common
divisor of two integers. </p>
<h3>Learning Objective 6.2.1 – Euclid’s Algorithm </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>explain and analyze Euclid’s algorithm for computing the greatest common divisor.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 31.2 of the textbook.</li>
<li>Do Exercise 31.2-3 from the textbook as part of Assignment 3. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_06_section_03"></a><h2>Section 6.3: Modular Algorithms</h2><h3>Learning Objective 6.3.1 – A Formal Model for Modular Arithmetic </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>describe a formal model for modular arithmetic within the framework of group theory.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 31.3 of the textbook.</li>
<li>Explain the following concepts:
<ul>
<li>Group</li>
<li>Abelian group</li>
<li>Finite group</li>
</ul>
</li>
<li>Do Exercise 31.3-1 from the textbook as part of Assignment 3. </li>
</ul>
<h3>Learning Objective 6.3.2 – Modular Linear Equations</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>solve modular linear equations.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 31.4 of the textbook.</li>
<li>Do Exercise 31.4-1 from the textbook as part of Assignment 3. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_06_section_04"></a><h2>Section 6.4: Chinese Remainder Theorem and Powers of an Element</h2><h3>Learning Objective 6.4.1 – Chinese Remainder Theorem</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>apply the Chinese remainder theorem.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 31.5 of the textbook.</li>
<li>Do Exercise 31.5-1 from the textbook as part of Assignment 3. </li>
</ul>
<h3>Learning Objective 6.4.2 – A Repeated-squaring Algorithm</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>Apply a repeated-squaring algorithm for efficiently computing <em>ab</em> mod <em>n</em>, given <em>a</em>, <em>b</em>, and <em>n</em>.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 31.6 of the textbook.</li>
<li>Do Exercise 31.6-1 from the textbook as part of Assignment 3. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_06_section_05"></a><h2>Section 6.5: RSA Public-key Cryptosystem</h2><h3>Learning Objective 6.5.1 – RSA Public-key Cryptosystem</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>explain the RSA public-key cryptosystem.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 31.7 of the textbook.</li>
<li>View this recommended video: <a href="http://youtu.be/ejppVhOSUmA">http://youtu.be/ejppVhOSUmA</a></li>
<li>Explain the following concepts:
<ul>
<li>Digital signature</li>
<li>RSA public key</li>
<li>RSA private key</li>
</ul>
</li>
<li>Do Exercises 31.7-1 from the textbook as part of Assignment 3. </li>
</ul>
<h1>Assignment 3</h1>
<p>It’s time to submit the problem set for Assignment 3 on the course home page.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_07"></a><h2>Unit 7: NP-completeness</h2><p>The
Millennium Prize Problems are seven problems in mathematics presented
by the Clay Mathematics Institute in 2000. As of December 2012, six of
the problems remained unsolved. A prize of US$1,000,000 is offered by
the institute for correct solutions. The Poincaré conjecture is the only
Millennium Prize Problem to be solved so far, by Grigori Perelman, who
declined the award in 2010.</p>
<p>The seven problems are as follows:</p>
<ol>
<li>P versus NP problem </li>
<li>Hodge conjecture </li>
<li>Poincaré conjecture (solved)</li>
<li>Riemann hypothesis </li>
<li>Yang–Mills existence and mass gap </li>
<li>Navier–Stokes existence and smoothness </li>
<li>Birch and Swinnerton–Dyer conjecture </li>
</ol>
<p>The first problem relates to our topic for Unit 8—NP-completeness.
The question is whether, for all problems for which an algorithm can <em>verify</em> a given solution quickly (that is, in polynomial time), an algorithm can also <em>find</em>
that solution quickly. The former describes the class of problems
termed NP, while the latter describes P. The question is whether or not
all problems in NP are also in P. This is generally considered one of
the most important open questions in mathematics and theoretical
computer science, as it has far-reaching consequences for other
problems in mathematics, and in biology, philosophy, and cryptography
(see P versus NP problem, proof consequences). </p>
<p>Most mathematicians and computer scientists expect that P ≠ NP.</p>
<p>The unit has two sections.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_07_section_01"></a><h2>Section 7.1: P ≠ NP Question</h2><h3>Learning Objective 7.1.1 – Polynomial Time</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>formalize the notion of <em>problem</em>, and define the complexity class P of polynomial-time solvable decision problems.</li>
<li>determine how these notions fit into the framework of formal-language theory. </li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Pages 1048-1053 and Section 34.1 of the textbook.</li>
<li>Explain the following concepts:
<ul>
<li>abstract problem</li>
<li>decision problem</li>
<li>optimization problem</li>
<li>encoding </li>
<li>concrete problem </li>
<li>polynomial-time solvable</li>
<li>complexity class P</li>
<li>alphabet, language</li>
<li>A language is <em>accepted</em> in polynomial time.</li>
<li>A language is <em>decided</em> in polynomial time. </li>
</ul>
</li>
<li>Do Exercises 34.1-1 and 34.1-4 from the textbook as part of Assignment 4.</li>
</ul>
<h4>Discussion Questions</h4>
<ol>
<li>Do you agree that the concept of a reduction is the central tool for analyzing the difficulty of a problem?</li>
<li>Why do we generally regard <em>the polynomial-time solvable problems</em> as tractable, but for philosophical, not mathematical, reasons? </li>
<li>Why should we use a formal-language framework to discuss solvability of decision problems?</li>
<li>Why do we focus on the concept of “problem” instead of “algorithm” in this unit?</li>
</ol>
<p>Post a response, and comment on other students' responses to earn
participation marks and develop your skills as an online communicator
in the profession.</p>
<h3>Learning Objective 7.1.2 – Optimization and Decision Problems</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>define the class NP of decision problems whose solutions are verifiable in polynomial time.</li>
<li>formally pose the P≠ NP question.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 34.2 of the textbook.</li>
<li>Do Exercises 34.2-1 and 34.2-8 from the textbook as part of Assignment 4. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_07_section_02"></a><h2>Section 7.2: NP-completeness</h2><h3>Learning Objective 7.2.1 – Polynomial-time Reductions and NP-completeness</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>show we can relate problems via polynomial-time “reductions.” </li>
<li>define NP-completeness.</li>
<li>sketch a proof that one problem is NPC.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 34.3 of the textbook.</li>
<li>Explain the following concepts:
<ul>
<li>polynomial-time reducible</li>
<li>NP-complete</li>
<li>NP-hard</li>
</ul>
</li>
<li>Do Exercise 34.3-1 from the textbook as part of Assignment 4. </li>
</ul>
<h3>Learning Objective 7.2.2 – NP-completeness Proofs</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>show how to prove other problems to be NPC much more simply by the methodology of reductions.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 34.4 of the textbook.</li>
<li>Do Exercise 34.4-1 from the textbook as part of Assignment 4. </li>
</ul>
<h3>Learning Objective 7.2.3 – Proving Problems NP-complete</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>show that a variety of problems are NP-complete.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Sections 34.5.1 and 34.5.2 of the textbook.</li>
<li>Do Exercise 34.5-1 from the textbook as part of Assignment 4. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr><a name="unit_08"></a><h2>Unit 8: Approximation Algorithms</h2><p>This unit shows you how to find approximate solutions to NP problems efficiently by using approximation algorithms. </p>
<p>The unit has four sections.</p>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_08_section_01"></a><h2>Section 8.1: Performance Ratios</h2><h3>Learning Objective 8.1.1 – Basic Terms</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>define the basic terms relating to approximation algorithms.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Pages 1106-1107 of the textbook.</li>
<li>Explain the following terms:
<ul>
<li>approximation ratio</li>
<li>ρ(n)-approximation algorithm </li>
<li>approximation scheme</li>
<li>polynomial-time approximation scheme</li>
<li>fully polynomial-time approximation scheme</li>
</ul>
</li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_08_section_02"></a><h2>Section 8.2: The Vertex-cover Problem</h2><h3>Learning Objective 8.2.1 – An NPC Minimization Problem </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>discuss the vertex-cover problem, an NP-complete minimization
problem that has an approximation algorithm with an approximation ratio
2.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 35.1 of the textbook.</li>
<li>Do Exercises 35.1.1 and 35.1-2 from the textbook as part of Assignment 4. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_08_section_03"></a><h2>Section 8.3: The Set-covering Problem</h2><h3>Learning Objective 8.3.1 – A Greedy Heuristic</h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>show how to use a greedy heuristic as an effective
approximation algorithm for the set-covering problem, with a
logarithmic approximation ratio.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 35.3 of the textbook.</li>
<li>Do Exercises 35.3.1, and 35.3-3 from the textbook as part of Assignment 4. </li>
</ul>
<p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><a name="unit_08_section_04"></a><h2>Section 8.4: The Subset-sum Problem</h2><h3>Learning Objective 8.4.1 –A Polynomial-time Approximation Scheme </h3>
<p>When you have completed this objective, you should be able to</p>
<ul>
<li>discuss a fully polynomial-time approximation scheme for the subset-sum problem.</li>
</ul>
<h3>Required Activities</h3>
<ul>
<li>Study Section 35.5 of the textbook.</li>
<li>Do Exercises 35.5-2 and Problem 35-3 from the textbook as part of Assignment 4.</li>
</ul><p> </p><br><div class="top-bottom"> <p><a href="#top" title="top">TOP</a></p></div><hr>
</div>
<span class="cleanslate TridactylStatusIndicator TridactylModenormal">normal</span></body></html>
|
