CS 381: Introduction to the Analysis of Algorithms

List of Topics (By Week):

1. Framework for the analysis of algorithms; induction, recurrences, the big O notation

2. Divide-and-conquer (concept + a few examples)

3. Prune-and-search (concept + a few examples)

4. Linear time algorithm for selection and its applications

5. Lower bound proofs

6. Sequence comparisons, longest common subsequence

7. Pattern matching

8. Depth first and breadth first search algorithms; topological sort

9. Biconnected components

10. Strongly connected components

11. Shortest path algorithms, minimum cost-spanning trees

12. Union-find data structures, balanced tree structures

13. Matchings, network flows

14. Polygon problems, convex hull, closest pair

15. NP completeness