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 Section 10.5 can be safely skipped or glossed over – that section really just talks about adjacency lists and matrices, the two common ways to represent graphs.
- Folks in CS201 will find the material to be a longer read (due to concept being new) but not necessarily a harder read.
- Pay attention to the conceptual difference between (unrooted, undirected) trees in graph theory and the (usually rooted and directed) trees in CS201/data structures, especially for those who are in both classes at the same time.
- 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 NOT be skipped. It is easy to miss it because the subsection title starts with the word “Problem”.
