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.
Prerequistes: 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.
    (ABET/CAC Outcome A)
  • Students will be able to analyze the complexity of the fundamental graph algorithms.
    (ABET/CAC Outcome B)
  • Student will understand the concepts and prove memberships for the basic computational complexity classes.
    (ABET/CAC Outcome B)

Student Outcomes:

  ABET/CAC Outcome A An ability to apply knowledge of computing and mathematics appropriate to the program’s student outcomes and to the discipline.
  ABET/CAC Outcome B An ability to analyze a problem, and define the computing requirements appropriate to its solution.

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