Purdue University - Department of Computer Science - CS 381: Introduction to the Analysis of Algorithms

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

Last Updated: Apr 25, 2017 4:47 PM

Department of Computer Science, 305 N. University Street, West Lafayette, IN 47907

Phone:(765) 494-6010 • Fax: (765) 494-0739

Copyright © 2016 Purdue University | An equal access/equal opportunity university | Copyright Complaints

Trouble with this page? Disability-related accessibility issue? Please contact the College of Science.