CSE373


Course

CSE373

Title

Analysis of Algorithms

Credits

3

Course Coordinator

Steven S. Skiena

Current Catalog Description

Introduction to the design and analysis of computer algorithms. Topics include searching, sorting, data structures, dynamic programming, and graph algorithms. Time and space complexity. Upper-bound, lower-bound, and randomized analysis. Introduction to NP completeness.

Prerequisite

MAT 211 or AMS 210; CSE 214

Course Goals
  • Provide a rigorous introduction to worst-case asymptotic algorithm analysis.
  • Develop classical graph and combinatorial algorithms for such problems as sorting, shortest paths and minimum spanning trees.
  • Introduce the concept of computational intractability and NP completeness.
Textbook

Fundamentals of Algorithmic, Gilles Brassard and Paul Bratley, Prentice Hall ISBN: 0-13-335068-1

The Algorithm Design Manual, Steven Skiena, Springer-Verlag, NY 1997

Major Topics Covered in Course
  • Preliminaries: Algorithm correctness, asymptotic (big-Oh) notation, problem modeling , (1.5 weeks)
  • Data Structures: Review of elementary data structures (stacks/queues), dictionary data structures such as binary search trees, priority queues such as heaps, (1.5 weeks)
  • Sorting: Algorithmic applications of sorting, analysis of quicksort, mergesort, and heapsort, distribution/radix sorting, lower bounds, (1.5 weeks)
  • Problem Decomposition Algorithms: Dynamic programming (edit distance, chain matrix multiplication), divide-and-conquer algorithms (binary search and variants), (1.5 weeks)
  • Combinatorial Search: Backtracking, exhaustive search, permutations/subsets, (1 week)
  • Graph Algorithms: graph data structures (adjacency lists/arrays), BFS/DFS, topological sorting, connectivity testing, minimum spanning trees, shortest paths (Dijkstra's and Floyd's algorithms), (3 weeks)
  • Intractability: problem reductions, NP-completeness, approximation algorithms, (2 weeks)
Laboratory Projects

 

Course Webpage

http://www.cs.sunysb.edu/~cse373