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.
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
