University of Canterbury
Algorithms
COSC262
Iowa State Course Substitution
Introduction to the Design and Analysis of Algorithms
COM S 311
Course Info
International Credits:
15.0
Converted Credits:
4.0
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)
Review
- Evaluation Date:
- September 6, 2019
- Evaluated:
- David Fernandez-Baca
- Comments:
-
Looks equivalent to CS 311, but would like to verify this upon students return.