3
$\begingroup$

During our year-end exit interviews with our outgoing seniors, the students made an explicit request to include some graph theory within our curriculum. This seems like an excellent idea, but the only place where we can fit it is in AP CS A1.

Obviously, graph theory is not within the AP curriculum per se, but I wonder if there is some way to shoe-horn at least a bit of it into a lab somewhere. Even so, I am having trouble finding a spot within the AP curriculum. Obviously, AP CS A focuses a great deal on arrays, loops, and objects. There's not a heavy emphasis on recursion (though it is present). Is there somewhere where graph theory can find some kind of "fit" within an AP class?

1 I'm unable to find a clean, succinct list of topics covered in AP for those unfamiliar, but this teacher's site has a list of unit headings that could serve as a very quick overview.

Improve this question
$\endgroup$
4
  • $\begingroup$ To those who might not be familiar with ap cs a curriculum, could you please give a link (perhaps in a comment, as it is not overly needed in the question itself) to a list of subjects covered? $\endgroup$
    – ItamarG3
    Jun 13, 2017 at 11:56
  • $\begingroup$ (unable to edit the comment anymore, but it's still useful, to explain why there's need for a footnote in your question) The footnote works just fine, thanks. $\endgroup$
    – ItamarG3
    Jun 13, 2017 at 15:34
  • 1
    $\begingroup$ Here is the course description as of 2014: secure-media.collegeboard.org/digitalServices/pdf/ap/… $\endgroup$
    – Matthew Fahrenbacher
    Jun 13, 2017 at 17:25
  • $\begingroup$ Add it after they take the AP test. We have a couple weeks of school after the test. $\endgroup$
    – d-cubed
    Jun 13, 2017 at 18:11

3 Answers 3

Reset to default
4
$\begingroup$

You may very well have some examples where you can discuss state machines and hence state diagrams, that is, graphs.

For example, if you're creating a game with a computer controlled character, that character might be in different states: pursue, search, attack <-- you can introduce a graph representing the states and transitions.

I wrote about this a bit here: https://cestlaz.github.io/posts/2012-12-17-layers-of-a-lesson.html

If you have a class that goes beyond the APCS-A curriculum and do more recursion, you can look at a maze solver (as I do), knights tour, etc - this lets you discuss searching the state space graph - DFS (and allude to alternatives including heuristic search and such), paths, etc. You can also talk about circuits and cycles (knights tour variants)

Improve this answer
$\endgroup$
0
2
$\begingroup$

I think the best place it could go would be whenever 2D arrays are introduced. You could use them to represent the adjacency matrix of a graph and use that to begin answering all kinds of graph theory questions.

You potentially could also cover it after going through class design and ArrayLists if you want to create a Vertex, Edge, and Graph classes... but I think this might get a little too complicated for AP A (they haven't even done LinkedLists yet!)

Improve this answer
$\endgroup$
2
  • $\begingroup$ The question seemed a bit odd. Does the OP have a plethora of students scoring 5? If so that's an anomaly and congrats. Certainly, we can use many topics to explore CS, but time is short in a CS AP class and there's a lot to be covered. Perhaps, the time might be better spent exploring the topics covered on the AP test more thoroughly? Perhaps an array game? $\endgroup$
    – d-cubed
    Jun 13, 2017 at 18:10
  • $\begingroup$ We do, indeed. We have an usual program with a HS CS "major", along with a 4-year core CS curriculum. My AP CS A kids enter the course about half a year ahead. They also simultaneously take a separate CS course, so they are learning linked list, trees, and some low-level concepts. This means that, though I cover the AP curriculum, I have a lot of latitude (and a duty!) to include other important concepts. $\endgroup$
    – Ben I. ♦
    Jun 13, 2017 at 18:24
0
$\begingroup$

After 2D arrays is a good place. We have them represent the adjacency matrix of a graph and create an adjacency list. The students work through Warshall's, Floyd's, and Dijkstra's algorithms. Then we wrap up with implementing DFS and BFS.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science Educators. This might be a very good answer, but it could really benefit from some explanations and details. Could you add some details and explanations or examples on how to integrate your suggestion into the ap cs a curriculum? $\endgroup$
    – ItamarG3
    Jul 23, 2017 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.