CS303: Algorithms

Unit 6: Graph Theory and Graph Algorithms

• Upon successful completion of this unit, you will be able to:

  • Describe concepts in graph theory, graph-based algorithms, and their analysis.
  • Describe tree-based algorithms and their analysis.

• 6.1: Introduction to Graph Theory

  • University of California, San Diego: Edward A. Bender and S. G. Williamson's "Basic Concepts in Graph Theory" URL

    Read this chapter for an introduction to graph theory.
    

• 6.2: Paths in Graphs

  • University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's "Paths in Graphs" URL

    Read Chapter 4 from S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
    

• 6.3: Graph Data Structures

  • PatrickJMT: "Graph Theory - An Introduction" Page

    Watch this video to learn about data structures used in graph algorithms.
    

• 6.4: Graph Theory Algorithms - Part I

  • Massachusetts Institute of Technology: Dr. Charles E. Leiserson's "Greedy Algorithms, Minimum Spanning Trees" Page

    Watch this video to learn about graph theory concepts, greedy algorithms, and minimum spanning trees.
    

• 6.5: Graph Theory Algorithms - Part II

  • Massachusetts Institute of Technology: Dr. Charles E. Leiserson's "Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search" Page

    Watch this video to learn about shortest path problems.
    

  • Graph Theory and Graph Algorithms Assignment URL

    Complete all questions in this assignment. There is one question on the breadth-first search implementation and one on depth-first search implementation. You can check your answers against the Answer Key.