COSC 3101.03
Design and Analysis of Algorithms
Section A Fall Tue, Thu 16:00-17:30
Section M Winter Tue 19:00-22:00
This course is intended to teach students the
fundamental techniques in the design of algorithms and
the analysis of their computational complexity. Each
of these techniques are applied to a number of widely
used and practical problems. At the end of this course,
a student will be able to: choose algorithms appropriate
for many common computational problems; to exploit
constraints and structure to design efficient algorithms;
and to select appropriate tradeoffs for speed and space.
Various program animation softwares may also be used
as an interactive pedagogical tool in the course.
Topics covered may include the following.
- Review: fundamental data structures, asymptotic
notation, solving recurrences.
- Sorting and order statistics: heapsort and priority
queues, randomized quicksort and its average case
analysis, decision tree lower bounds, linear-time
selection.
- Divide-and-conquer: binary search, quicksort,
mergesort, polynomial multiplication, arithmetic
with large numbers.
- Dynamic Programming: matrix chain product,
scheduling, knapsack problems, longest common
subsequence, some graph algorithms.
- Greedy methods: activity selection, some graph
algorithms.
- Amortization: the accounting method, eg, in
Graham's Scan convex hull algorithm.
- Graph algorithms: depth-first search, breadth-first
search, biconnectivity and strong connectivity,
topological sort, minimum spanning trees, shortest
paths.
- Theory of NP-completeness.
Texts: t.b.a.
Suggested reading:
- T.H. Cormen, C.E. Leiserson, R.L. Rivest,
Introduction to Algorithms, McGraw-Hill and The
MIT Press, 1991.
- P. Gloor, S. Dynes, I. Lee, Animated Algorithms
CD-ROM, The MIT Press 1993.
- D.E. Knuth, The Stanford GraphBase: A platform
for combinatorial computing, Addison-Wesley &
The ACM Press, 1993.
Prerequisites: general
prerequisites, including
MATH2320.03 (SCS students may enrol without
MATH2320.03 or concurrently with MATH2320.03)