COMPENG 3SM4 - Algorithm Design and Analysis

4 unit(s)

Design and analysis of correct and efficient algorithms and related discrete mathematics concepts and data structures. Topics include: sets, function relations; graph theory; graph algorithms (graph traversals, topological sort, minimum spanning trees, shortest paths); balanced trees and advanced data structures; algorithmic design strategies (dynamic programming, greedy algorithms, divide-and-conquer, backtracking); introduction to NP completeness and approximation algorithms; introduction to parallel algorithms.
Three lectures, one tutorial, one lab every other week; second term
Prerequisite(s): COMPENG 2SH4, and COMPENG 2SI4 or COMPENG 2SI3
Antirequisite(s): COMPSCI 2C03