COMP 272 or an equivalent data-structures course. Knowledge and skills in Java, C/C++, or Python programming. Knowledge of high school mathematics (MATH 30 level) is assumed.
Course start date:
If you are a:
Self-funded student: register by the 10th of the month, start on the 1st of the next.
Students who are concerned about not meeting the prerequisites for this course are encouraged to contact the course coordinator before registering.
Overview
Algorithms form the core of most technologies used in contemporary computers, and their practical applications are ubiquitous.
COMP 372 introduces the fundamental techniques for designing and analyzing algorithms. These include asymptotic notation and analysis, divide-and-conquer algorithms, dynamic programming, greedy algorithms, graph algorithms, number-theoretic algorithms (e.g., RSA cryptosystem), NP-completeness, and approximation algorithms. This course also emphasizes techniques for constructing efficient algorithms and for analyzing the efficiency of an algorithm.
The algorithms in the course are described in English and in pseudocode, which is readable by anyone with basic knowledge of programming.
Outline
COMP 372 consists of seven units:
Unit 1: Foundations
Unit 2: Divide-and-Conquer Algorithms
Unit 3: Dynamic Programming and Greedy Algorithms
Unit 4: Elementary Graph Algorithms
Unit 5: Number-Theoretic Algrotithms
Unit 6: NP-Completeness
Unit 7: Approximation Algorithms
Learning outcomes
Upon successful completion of this course, you should be able to
describe the major modern algorithms and techniques that are essential to today’s computers.
identify the key characteristics of a given problem and analyze the suitability of a specific algorithm design technique for the problem.
apply algorithms and design techniques to solve problems, typically using the following algorithms:
divide-and-conquer algorithms
dynamic programming
greedy algorithms
graph algorithms
number-theoretic algorithms
NP-completeness
approximation algorithms
mathematically evaluate the quality of solutions from an algorithm.
implement an algorithmic solution for a given problem in high-level programming languages.
Evaluation
To receive credit for COMP 372, you must achieve a course composite grade of at least D (50 percent), an average grade of at least 50 percent from the combined marks of the assigments and the final project, and at least 50 percent on the final examination. The weighting of the composite grade is as follows:
Activity
Weight
Assignment 1
5%
Assignment 2
5%
Assignment 3
5%
Assignment 4
7%
Assignment 5
5%
Assignment 6
5%
Assignment 7
3%
Final Project
20%
Participation
5%
Final Examination
40%
Total
100%
The final examination for this course must be requested in advance and written under the supervision of an AU-approved exam invigilator. Invigilators include either ProctorU or an approved in-person invigilation centre that can accommodate online exams. Students are responsible for payment of any invigilation fees. Information on exam request deadlines, invigilators, and other exam-related questions, can be found at the Exams and grades section of the Calendar.
To learn more about assignments and examinations, please refer to Athabasca University’s online Calendar.
Materials
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press. (Print)
Challenge for credit
Overview
The challenge for credit process allows you to demonstrate that you have acquired a command of the general subject matter, knowledge, intellectual and/or other skills that would normally be found in a university-level course.
Full information about challenge for credit can be found in the Undergraduate Calendar.
Evaluation
To receive credit for the COMP 372 challenge registration, you must achieve a grade of at least 50 percent on the project and D (50 percent) on the examination. The weighting of the composite grade is as follows:
Athabasca University reserves the right to amend course outlines occasionally and without notice. Courses offered by other delivery methods may vary from their individualized study counterparts.