Computer Science (COMP) 372

Design and Analysis of Algorithms (Revision 1)

COMP 378 Course website

Delivery Mode: Individualized study online

Credits: 3

Area of Study: Science

Prerequisite: COMP 272 or an equivalent data structures course. Knowledge and skills in Java or C or Python programming. Knowledge of high school mathematics (MATH 30 level) is assumed.

Faculty: Faculty of Science and Technology

Centre: School of Computing and Information Systems

COMP 372 has a Challenge for Credit option.

check availability

**Note: Students who are concerned about not meeting the prerequisites for this course are encouraged to contact the course coordinator before registering

Overview

Algorithms are the core of most technologies used in contemporary computers. Practical applications of algorithms are ubiquitous.

COMP 372 introduces the fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms, greedy algorithms, dynamic programming, multithreaded algorithms, number-theoretic algorithms and RSA cryptosystem, NP-completeness, and approximation algorithms. This senior-level course 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 that is readable by anyone who has done a little programming.

Learning Outcomes

Upon successful completion of the course, you will be able to

  • describe the major modern algorithms and selected techniques that are essential to today’s computers.
  • decide on the suitability of a specific algorithm design technique for a given problem.
  • apply the algorithms and design techniques to solve problems, and mathematically evaluate the quality of the solutions;

Course Outline

The course consists of the following nine units.

Unit 0 - Orientation

Unit 1 - Foundations

  • Problems
  • Complexity
  • Analysis
  • Asymptotic notation

Unit 2 - Divide-and-Conquer Algorithms

  • The maximum-subarray problem
  • Strassen’s algorithm for matrix multiplication
  • Methods for solving recurrences

Unit 3 - Dynamic Programming and Longest Common Subsequence

  • Rod cutting
  • Matrix-chain multiplication
  • Elements of dynamic programming
  • Longest common subsequence

Unit 4 - Greedy Algorithms

  • Greedy approach
  • Data-compression (Huffman) codes

Unit 5 - Multithreaded Algorithms

  • Dynamic multithreading model
  • Metrics of work, span, and parallelism
  • Matrices multiplication with multithreading

Unit 6 - Number-theoretic Algorithms and RSA Cryptosystem

  • Basic concepts
  • Euclid's algorithm
  • Modular algorithm
  • Repeated-squaring algorithm
  • RSA public-key cryptosystem

Unit 7 - NP-completeness

  • NP question
  • NP-completeness

Unit 8 - Approximation Algorithms

  • Performance ratio
  • The vertex-cover problem
  • The set-covering problem
  • The subset-sum problem

Evaluation

To receive credit for COMP 372, you must achieve a course composite grade of at least “D” (50 percent), and a grade of at least 50 percent on the invigilated final examination, and an average grade of at least 50 percent from the combined marks of the Assignments and Project. The weighting of the composite grade is as follows:

Assignment 1 (problem set 1) Assignment 2 (problem set 2) Assignment 3 (problem set 3) Assignment 4 (problem set 4) Assignment 5 (project) Participation Final Exam Total
10% 15% 15% 15% 15% 5% 25% 100%

To learn more about assignments and examinations, please refer to Athabasca University's online Calendar.

Course Materials

Textbook

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Other Resources

The remaining learning materials are also distributed in electronic format. At this time, those materials include

  • the units of the study guide
  • detailed descriptions of the requirements for the individual assignments
  • a course evaluation form

Additional supporting materials of interest to students may be made available through the course website.

Special Course Features

Computer Science 372: Design and Analysis of Algorithms is offered in unpaced electronic mode. Electronic unpaced study is facilitated through a variety of computer-mediated communication options and can be completed at the student's workplace or home.

Challenge for Credit Course Overview

The Challenge for Credit process allows students to demonstrate that they 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 for the Challenge for Credit can be found in the Undergraduate Calendar.

Challenge Evaluation

To receive credit for the COMP 372 challenge registration, you must achieve a grade of at least 75% on the assignment and "B" (75%) on the challenge examination. The weighting of the composite grade is as follows:

Assignment Final Examination Total
50% 50% 100%

Undergraduate Challenge for Credit Course Registration Form

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.

Opened in Revision 1, March 3, 2014.

Updated May 10 2016 by Student & Academic Services