CSE 3101 3.0 Design and Analysis of Algorithms

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 is 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.
<p> Topics covered may include the following:
<ul>
<li>
Review: fundamental data structures, asymptotic notation, solving
recurrences, Sorting and order statistics: heapsort and priority queues, randomised quicksort and its average case analysis, decision tree lower bounds, linear-time selection
<li>
Divide-and-conquer: binary search, quicksort, mergesort, polynomial multiplication, arithmetic with large numbers
<li>
Dynamic Programming: matrix chain product, scheduling, knapsack problems, longest common subsequence, some graph algorithms
<li>
Greedy methods: activity selection, some graph algorithms
<li>
Amortisation: the accounting method, e.g., in Graham's Scan convex hull algorithm
<li>
Graph algorithms: depth-first search, breadth-first search, biconnectivity and strong connectivity, topological sort, minimum spanning trees, shortest paths
<li>
Theory of NP-completeness
</ul>
Suggested reading:
<ul>
<li>
T.H. Cormen, C.E. Leiserson, R.L. Rivest, "Introduction to Algorithms",
2nd edition, McGraw-Hill and The MIT Press, 2001. 
<li>
Jeff Edmonds. notes: "How to Think about Algorithms"
</ul>
Course Learning Outcomes
<ul>
<li>
    CLO 1  Choose an appropriate algorithm to solve a given computational
    problem, and justify that choice
<li>
    CLO 2    Design new algorithms using a variety of techniques (recursion,
    greedy algorithm, dynamic programming, backtracking)
<li>
    CLO 3  Prove correctness of an algorithm using pre- and post-conditions
    and loop invariants
<li>
    CLO 4    Prove bounds on the running time of an algorithm
<li>
    CLO 5    Apply standard graph algorithms to a variety of problems
</ul>
Prerequisites: General prerequisites, CSE2001 3.0, MATH1090 3.0, MATH1310 3.0