Computer Science 372: Design and Analysis of Algorithms
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:
The course consists of the following nine units.
Unit 0 - Orientation
Unit 1 - Foundations
Unit 2 - Divide-and-Conquer Algorithms
Unit 3 - Dynamic Programming and Longest Common Subsequence
Unit 4 - Greedy Algorithms
Unit 5 - Multithreaded Algorithms
Unit 6 - Number-theoretic Algorithms and RSA Cryptosystem
Unit 7 - NP-completeness
Unit 8 - Approximation Algorithms
Upon successful completion of this course, you should be able to
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 remain subscribed to the COMP 372 General Discussion Forum.
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.
When designing an algorithm there are two fundamental issues to be considered: correctness and efficiency. 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.
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.
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.
There are policies and service standards that specify how you may contact us and how soon you should expect a reply. We take those standards seriously.
This course is like other undergraduate courses at Athabasca University in that it is unpaced. 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.
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 Coordinator’s COMP372 web page from time to time.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
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.
If you use the work of others, whether explicitly using the same content or basing your ideas on theirs, you must properly list and cite your sources in all 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.
The good news is that there is plenty of information online to help avoid this happening, including our own Write Site, 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.
First of all, tell them 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.
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.
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 References section that lists all the sources you need to cite in your journal.
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 Write Site.
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.
This course makes extensive use of Wikipedia articles as learning resources to help frame ideas and discussions. We do this because Wikipedia 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.
However, you should never rely solely on Wikipedia 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 Wikipedia articles, or you might search for topics that suggest themselves in Wikipedia in more diverse places, especially scholarly articles such as can usually be found through Google Scholar (http://scholar.google.com) or Microsoft's rather less well developed Academic Search (http://academic.research.microsoft.com). Remember the mantra—"Wikipedia is a great place to start and a terrible place to finish."
Please note that Wikipedia 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 Wikipedia articles as referenced resources. Indeed, you should avoid citing any encyclopaedia or dictionary at all, for much the same reasons. This includes Encyclopaedia Britannica.
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.
The five assignments are worth 70% of the final grade:
Assignment 1: Problem Set 1 – Submit all your solutions to the selected exercises in Chapters 1, 2, 3 and 4 of the textbook after completing Unit 2.
Assignment 2: Problem Set 2 – Submit all your solutions to the selected exercises in Chapters 15 and 16 of the textbook after completing Unit 4.
Assignment 3: Problem Set 3 – Submit all your solutions to the selected exercises in Chapters 27 and 31 of the textbook after completing Unit 6.
Assignment 4: Problem Set 4 – Submit all your solutions to the selected exercises in Chapters 34 and 35 of the textbook after completing Unit 8.
Assignment 5: Project – You should submit the project before writing the final exam.
Throughout this course, when you are asked to present an algorithm, this means that you need to do three things:
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.
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.
From the Athabasca University document on Academic Integrity:
“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.”
I also refer everyone to the Student Code of Conduct, specifically Academic Misconduct:
http://calendar.athabascau.ca/undergrad/current/page11.php#acad_misconduct
Specifically, you cannot copy text from a source and present it as your own words.
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 http://owl.english.purdue.edu/owl/resource/560/01/ for examples of how to list and cite sources using APA style, which is acceptable for COMP 372.
http://calendar.athabascau.ca/undergrad/page11_03_new.php
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. All instances of plagiarism will be reported to the Dean of Faculty of Science and Technology.
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.
Warning: Plagiarism detection software may be used on submitted assignments to insure compliance.
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:
https://www.umgc.edu/current-students/learning-resources/academic-integrity/tutorial/index.cfm
If you have any questions about plagiarism, please post them on the COMP 372 General Discussion Forum for discussion.
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.
This unit addresses the following topics of interest:
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.
The unit has three sections.
Your goals for this section are
When you have completed this objective, you should be able to
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.
Your goal for this section is to familiarize yourself with the framework that we will use throughout the course.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
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): http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/1
When you have completed this objective, you should be able to
Your goals for this section are
When you have completed this objective, you should be able to
For supplemental material, I recommend that you watch this video: http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/2
When you have completed this objective, you should be able to
What are the common abuses in the basic asymptotic notations? Post your thoughts on this to the COMP 372 General Discussion Forum.
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.
For supplemental material, I recommend that you watch this video: http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/3
This unit will introduce
The unit has three sections.
Your goal for this section is to become familiar with the maximum-subarray problem and its divide-and-conquer algorithm.
When you have completed this objective, you should be able to
Your goal for this section is to become familiar with Strassen’s algorithm for matrix multiplication.
When you have completed this objective, you should be able to
Your goal for this section is to become familiar with the methods for solving recurrences.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
It’s time to submit the problem set for Assignment 1 on the course home page in Moodle.
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to sub-problems. Why do we call it programming? In fact, programming in this context refers to a tabular method, not to writing computer code. The term dynamic programming 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 planning, and “dynamic programming” was conceived to optimally plan multistage processes.
Why do we need dynamic programming?
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!
The basic idea behind dynamic programming is eliminating overlapping recursive calls by using more memory to keep track of previous values.
I recommend that you to watch this video from http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/15
This unit will address the following topics of interest:
The unit has two sections.
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.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
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.
Your goal for this section is to learn how to find the longest common subsequence of two sequences via dynamic programming.
When you have completed this objective, you should be able to
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 choices is overkill.
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.
The idea of a greedy algorithm is to make each choice in a locally optimal manner.
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.
A greedy algorithm approach provides an optimal solution for many such problems much more quickly than would a dynamic programming approach. However, is this approach effective? This unit will introduce matroid theory, which provides a mathematical basis that can help us to show that a greedy algorithm yields an optimal solution.
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.
I recommend that you to watch this video:
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/
This unit addresses the following topics of interest:
The unit has only one section.
Your goal for this section is to become familiar with greedy algorithms and their applications.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
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.
It’s time to submit the problem set for Assignment 2 on the course home page.
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.
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.
And then we look at how to design 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.
This unit will
The unit has two sections.
When you have completed this objective, you should be able to
Post your thoughts on this to the COMP 372 General Discussion Forum.
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.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
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.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
It’s time to submit the problem set for Assignment 3 on the course home page.
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.
The seven problems are as follows:
The first problem relates to our topic for Unit 8—NP-completeness. The question is whether, for all problems for which an algorithm can verify a given solution quickly (that is, in polynomial time), an algorithm can also find 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).
Most mathematicians and computer scientists expect that P ≠ NP.
The unit has two sections.
When you have completed this objective, you should be able to
Post a response, and comment on other students' responses to earn participation marks and develop your skills as an online communicator in the profession.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
This unit shows you how to find approximate solutions to NP problems efficiently by using approximation algorithms.
The unit has four sections.
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to
When you have completed this objective, you should be able to