Enumerating Concepts
Our second step is to generate a list of the Concepts covered in
this course.
Sample Prompt
Please create a fully connected dependency graph
for learning the concepts in a college-level Graph Algorithms course.
In this step, for each Concept on this list below, create a new
list of other concepts on which it depends. If a concept
depends on a specific concept that is not listed,
then we will need to add it as a new concept.
This will help us determine the teaching order of the Concepts.
Return the new list as a CSV file using the following format:
1. The first column in the CSV file is a numeric concept
ID you assigned in the list above.
2. The second column is the concept name.
3. The third column is a pipe-delimited list of the Concept IDs that the concept depends upon.
Check your results to make sure that all concepts are connected to at least one other concept.
Foundation Concepts are concepts that have no dependant concepts in this set. They have an empty third column.
ChatGPT Response
Here is a numbered list of 150 core concepts for my course on graph algorithms, presented in the order they should be taught, from foundational to advanced:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150 | 1. Graph Definition
2. Nodes
3. Edges
4. Directed Graph (Digraph)
5. Undirected Graph
6. Weighted Graphs
7. Unweighted Graphs
8. Cyclic Graphs
9. Acyclic Graphs (DAG)
10. Graph Density
11. Degree of a Node
12. In-degree
13. Out-degree
14. Path
15. Walk
16. Cycle
17. Connected Graph
18. Disconnected Graph
19. Subgraph
20. Bipartite Graph
21. Complete Graph
22. Multigraph
23. Graph Isomorphism
24. Self-loop
25. Adjacent Nodes
26. Incident Edges
27. Graph Adjacency Matrix
28. Graph Adjacency List
29. Graph Incidence Matrix
30. Graph Traversal
31. Depth-First Search (DFS)
32. Breadth-First Search (BFS)
33. Stack (DFS)
34. Queue (BFS)
35. Backtracking
36. Recursion (DFS)
37. Shortest Path Problem
38. Dijkstra’s Algorithm
39. Bellman-Ford Algorithm
40. A* Search Algorithm
41. Floyd-Warshall Algorithm
42. All-Pairs Shortest Path (APSP)
43. Single-Source Shortest Path (SSSP)
44. Negative Weight Cycles
45. Minimum Spanning Tree (MST)
46. Kruskal’s Algorithm
47. Prim’s Algorithm
48. Union-Find Algorithm
49. Cycle Detection (MST)
50. Cut-Vertices
51. Bridges (Edge Cut)
52. Eulerian Path
53. Eulerian Circuit
54. Hamiltonian Path
55. Hamiltonian Cycle
56. Traveling Salesman Problem (TSP)
57. Approximation Algorithms (TSP)
58. Heuristics (TSP)
59. Graph Coloring
60. Chromatic Number
61. Greedy Coloring Algorithm
62. Clique
63. Maximum Clique Problem
64. Independent Set
65. Maximal Independent Set
66. Dominating Set
67. Vertex Cover
68. Minimum Vertex Cover
69. Planar Graphs
70. Graph Embedding
71. Kuratowski’s Theorem
72. Graph Minor Theorem
73. Graph Duality
74. Planarity Testing
75. Face of a Graph (Planar)
76. Topological Sorting
77. DAG Applications
78. Strongly Connected Components (SCC)
79. Tarjan’s Algorithm (SCC)
80. Kosaraju’s Algorithm (SCC)
81. Articulation Points
82. Bridge Finding Algorithm
83. Graph Matching
84. Bipartite Matching
85. Hopcroft-Karp Algorithm
86. Stable Matching Problem
87. Gale-Shapley Algorithm
88. Network Flow
89. Max Flow Problem
90. Ford-Fulkerson Algorithm
91. Edmonds-Karp Algorithm
92. Min-Cut Max-Flow Theorem
93. Push-Relabel Algorithm
94. Dinic’s Algorithm
95. Capacity Scaling Algorithm
96. Circulation Problem
97. Multi-Commodity Flow
98. Cut-Set
99. Cut-Set Theorem
100. Flow Decomposition
101. Flow Networks
102. Graph Partitioning
103. Graph Clustering
104. k-Cuts Problem
105. Modularity (Clustering)
106. Spectral Clustering
107. Girvan-Newman Algorithm
108. Louvain Method (Clustering)
109. Random Walk
110. Markov Chains (Graphs)
111. Pagerank Algorithm
112. HITS Algorithm
113. Centrality Measures
114. Degree Centrality
115. Betweenness Centrality
116. Closeness Centrality
117. Eigenvector Centrality
118. Katz Centrality
119. Graph Laplacian
120. Spectral Graph Theory
121. Cheeger’s Inequality
122. Expander Graphs
123. Graph Diameter
124. Graph Radius
125. Eccentricity
126. Graph Girth
127. Percolation Theory
128. Small-World Networks
129. Scale-Free Networks
130. Graph Randomization
131. Erdős–Rényi Model
132. Barabási–Albert Model
133. Watts-Strogatz Model
134. Community Detection
135. Block Models
136. Stochastic Block Model
137. Label Propagation Algorithm
138. Belief Propagation
139. Graph Neural Networks (GNN)
140. Node Embeddings
141. DeepWalk Algorithm
142. Node2Vec Algorithm
143. GraphSAGE
144. GCN (Graph Convolutional Network)
145. GAT (Graph Attention Network)
146. Graph Recurrent Neural Networks
147. Link Prediction
148. Graph Anomaly Detection
149. Knowledge Graphs
150. RDF vs LPG Models
|
This list progresses from basic graph theory concepts to more advanced topics like machine learning on graphs, ensuring that each concept builds on previous ones.