CS202 — Analysis of Algorithms (required)

Credits: 1 unit (4 credit hours)
Contact Hours: 3 lecture
Instructor: Professor Ge Xia
Last Taught: Fall 2013
Text Book: Algorithms By Dasgupta, Papadimitriou, and Vazirani. (McGraw-Hill, 2006.)
Description: The design and analysis of algorithms and their complexity. This course studies techniques for measuring algorithm complexity, fundamental algorithms and data structures, intractable problems, and algorithm-design techniques.
Prerequisites: CS150 (Data Structures and Algorithms) and
Math182 (Discrete Structures)

Specific Course Goals:

After successfully completing this course, the student will be able to:

  • Students will understand the concepts and be able to apply and analyze the divide-and-conquer approach.
  • Students will be able to analyze the complexity of the fundamental graph algorithms.
  • Student will understand the concepts and prove memberships for the basic computational complexity classes.

Student Outcomes:

ABET/CAC Outcome 1 Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions.

Topics covered:

  • Asymptotic notations
  • Complexity analysis
  • Recurrence
  • Divide-and-conquer approach and sorting algorithms
  • Graph representation and graph algorithms
    • Depth First Search
  • Topological sort
  • Strongly connected components
    • Breadth First Search
  • Dijkstra’s algorithm
  • Bellman-Ford algorithm
  • shortest path in DAG
  • all-pairs shortest path
  • Greedy algorithms
    • Minimum spanning tree
    • Huffman encoding
  • Dynamic programming
  • P and NP-complete Problems