May 13, 2021  
University of Alberta Calendar 2020-2021 
University of Alberta Calendar 2020-2021 [ARCHIVED CATALOG]

AUCSC 310 - Algorithm Design and Analysis

★ 3 (fi 6) (either term, 3-0-1.5) Trees, binary trees, search trees, their implementation, traversal, and search and update operations. Introduction to graph theory; data structures for the representation of graphs, digraphs, and networks, and their associated algorithms (traversal, connected components, topological sorting, minimum-spanning trees, shortest paths, transitive closure). Dynamic equivalence relations and union-find sets; amortized analysis. String matching. Algorithm design techniques (divide-and-conquer, dynamic programming, the greedy method). Merge-sort and the analysis of divide-and-conquer algorithms with recurrence relations; bucket-sort, ratix-sort, and the lower bound on sorting; comparison of sorting algorithms. Prerequisites: AUCSC 112 or 210 and AUMAT 250.