AUCSC 310 - Algorithm Design and Analysis

Science

3 units (fi 6)(EITHER, 3-0-1.5)

Augustana Faculty

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, radix-sort, and the lower bound on sorting; comparison of sorting algorithms. 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. Prerequisites: AUCSC 112, or AUCSC 211 and AUSCI 235; and AUMAT 250.