University of Canterbury



Iowa State Course Substitution

Design and Analysis of Algorithms

COM S 311

Course Info

International Credits: 15.0
Converted Credits: 4.0
Semester: spring
Country: New Zealand
Language: English
Course Description:
A selection of topics from the following (non-exclusive) list is covered: - Introduction to algorithmic thinking and design - Analysis of algorithms (proof techniques, asymptotic notation) - Graphs: Topological ordering, Minimum spanning trees, Single-source and All-pair shortest paths - Divide & conquer: design techniques and solving recurrences - Algorithms for linear time sorting - Backtracking: combinatorial search and generation - Computability: reductions and complexity classes - Greedy algorithms: Coin changing, Interval scheduling, Fractional knapsack, Huffman codes - Dynamic programming: Top-down approach, Bottom-up enumeration, Optimal substructure, Optimal coin changing, Minimum cost path in grid, Multi-stage graphs, Unbounded knapsack, 0/1 knapsack, Edit distance, Longest common subsequence, Dynamic time warping - String matching: Rabin-Karp algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm - Computational geometry: Convex hulls (properties, Gift-wrap algorithm, Graham-scan algorithm), Plane-sweep algorithms (closest pair, line intersections), Range search methods (kD trees, Quadtrees)


Evaluation Date:
September 6, 2019
David Fernandez-Baca

Looks equivalent to CS 311, but would like to verify this upon students return.