CMPT 370

THE KING'S UNIVERSITY

COURSE NUMBER:

CMPT 370

COURSE TITLE:

Algorithm Analysis

NAME OF INSTRUCTOR:

Michael Janzen

CREDIT WEIGHT AND WEEKLY TIME DISTRIBUTION:

3 credits (3 hrs lecture - 0 hrs seminar - 3 hrs lab)

COURSE DESCRIPTION:

Introduction to algorithm analysis, asymptotic notation, and different types of algorithmic techniques (divide and conquer, greedy methods, dynamic programming, backtracking and local search methods), fundamental algorithms for searching and sorting, merging, hashing and graphing. Analysis techniques to estimate program efficiency will also be considered.

Prerequisites: CMPT 276

COURSE TEXTBOOK:

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009), Introduction to Algorithms, 3rd Ed. The MIT Press.

MARK DISTRIBUTION IN PERCENT:

Laboratory Work	6%
Lecture Assignments	24%
Project	15%
Tests	30%
Final Exam	25%

	100%

COURSE OBJECTIVES:

This course is intended to introduce students to computer algorithms and their analysis.
By the end of this course a student should be able to

Explain some well known sorting, tree searching, and string searching algorithms
Analyze algorithms based on their time and space requirements

TOPIC OUTLINE:

Review of Data Structures
Introduction to Complexity Analysis
Searching and Sorting

Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap
Sort

Trees

Binary Trees, AVL Trees, Red-Black Trees

Graph Algorithms

Minimal Spanning Tree, Djikstra’s Algorithm, A* Search

Strings (Searching and Compression)

Huffman Codes, LZW

Additional Topics as Time Allows

Required texts, assignments, and grade distributions may vary from one offering of this course to the next. Please consult the course instructor for up to date details.