*This is a two-week module with 3 class meetings (2/28, 3/1, and 3/6). The 3/8 class meeting is for the EM (Graph Applications). *

**CS201, CS230, and CS330 ALL cover graphs and trees**. This is probably the most-overlapped topic within these 3 classes. However, the timing does not work out well for those who are taking CS201/230 at the same time: graphs and trees are usually the last part of CS201, and we cannot schedule our graph module after it. Instead, we will use a parallel approach: apart from the absolutely necessary (basic terminologies of graphs and trees), we try to **minimize overlap in content**. This implies we will **put less emphasis on** the following topics in CM6:

*Binary search trees and its traversal**Depth-first search (DFS) and Breadth-first search (BFS) on general graphs**Shortest path***algorithms**(but we will discuss shortest paths as a mathematical concept)

*It is hard to completely avoid discussing these topics altogether, but when we do, we will focus on graph theory concepts/high-level ideas. CS201/330 is/was/will be where you learn the details of graph algorithms. The graph applications EM will also cover some of them.*

*There are two parts of required readings for this module, each corresponding to a prepare quiz. *

*This post covers the first part. The second part is covered in CM6: Required Reading Part II.*

- Reading Part I: AIDMA
**Chapter 10**– corresponding to CM6: Graph Fundamentals Prepare Quiz I.- If you have taken CS201, the first few subsections should be a quick brush up, and
– that section really just talks about adjacency lists and matrices, the two common ways to represent graphs.*Section 10.5 can be safely skipped or glossed over* - Folks in CS201 will find the material to be a
*longer*read (due to concept being new) but not necessarily a harder read. , especially for those who are in both classes at the same time.*Pay attention to the conceptual difference between (unrooted, undirected) trees in graph theory and the (usually rooted and directed) trees in CS201/data structures*

- If you have taken CS201, the first few subsections should be a quick brush up, and
- Several notes:
- In Definition 10.16, it is better to use the subset notation with equality (⊆) for both parts. We do want a graph to be a subgraph of itself, and AIDMA does not make that clear.
**Section 10.6 (Problem Solving with Graphs) is part of the reading and should**It is easy to miss it because the subsection title starts with the word “Problem”.*NOT*be skipped.