Learning Bipartite Graph
© 21 Sep 2011 Luther Tychonievich
Licensed under Creative Commons: CC BY-NC-ND 3.0
other posts


Reflections on instruction and understanding.


I wrote several weeks ago about watching Salman Khan’s 2011 TED talk. In that post I discussed the question “‍What should teachers do?‍”, one of two thoughts inspired by his video; the other, knowledge dependency graphs, is the subject of this post.

At one point in his TED talk, Kahn displays a knowledge dependency graph. Addition depends on counting, multiplication on addition, and so on. This is the closest thing I’ve seen yet to an idea that came to me something over a years ago, which I originally thought of as learning petri nets though bipartite graphs might be a better word than petri nets. Don’t worry if those terms are strange to you; I’ll build up to them in this post.

“‍… but what about lesson plans?‍”

Each summer I assist in the running of the Tapestry Workshop, a teacher development workshop aimed at improving high-school computer science education. Two years ago during one of the dinners I was sitting at a table with a teacher named Scott Portnoff who commented that our high-level instruction was all well and good but in the end of the day he needed to have a lesson plan for every lesson every class every week throughout the year. Getting the information we shared down to that level was daunting.

I spent a few months pondering that idea. I don’t like the idea of a single structured curriculum; it stifles creativity, makes it hard to adjust to student interest, etc. But I also recognized that even even for skilled and experienced teachers like Portnoff the task of crafting 180 lessons a year was a major time drag, time that might better be spent recruiting students or preparing engaging activities in class or reviewing current trends in the field and coming up with a few good lessons to incorporate them into the classroom.

As I considered this problem I realized what I wished existed was a database of lesson ideas that teachers could submit to, pull from, and comment on. Something like a wiki of curricula. But the problem there was the prerequisites for each lesson, and not just the tangible prerequisites like “‍must know how to multiply‍” but also the intangibles like “‍assumes familiarity with logic group activities‍” or “‍assumes students care about football.‍”

And from that was born my view of a data structure for instruction.

Bipartite Graphs for Instruction

unfinished ideas

A graph is a mathematical structure that has a set of nodes connected by a set of edges. For example, I might model a roadway as a graph with intersections as nodes and roads as edges. A bipartite graph is a graph where you can split the nodes into two groups, such that all edges go between the two partitions. If I make both roads and intersections nodes and add edges from each intersection to its roads then I have a bipartite graph: roads connect to intersections, intersections connect to roads. Graphs can be directed: for example, in a road graph I might handle one-way streets as edges that only go one way. They might also contain loops or self-edges, such as we might have in a dead-end traffic roundabout where an intersection leads back to itself.

Now let us consider a bipartite graph where some nodes are instructional activities and the others are student familiarity. In such a graph, I can mark all the familiarity nodes that students have learned and then am free to use any of the lessons that depend only on those nodes. A lesson that is designed reinforce a concept will have edges too the same concepts it has lessons from. …But I can feel the reader becoming confused. Let me give an example.

In the above graph we have three instructional activities and six student familiarities. All of the activities result in greater familiarity with addition. Two of them introduce addition using counting or memorization; one reinforces addition assuming some prior knowledge of the topic.

I would expect a full version of such a graph would have, in addition to many more nodes and edges, some hierarchical grouping of nodes. A lesson, for example, could be a collection of activities, or a “‍field‍” like arithmetic a collection of familiarities. I would also expect that edges could be given different weights, representing the importance of a prerequisite or emphasis of on a new concept.

Uses of Instruction Graphs

I believe that these graphs serve many ends. My initial idea of a lesson plan wiki is certainly one. I also expect that the process of creating such a graph for a course outline will reveal to the instructor ways of organizing information that had not previously been considered. Further, I suspect that students would benefit from discovering the context of a lesson with an explicit reminder of what concepts they ought to remember.

Looking for comments…

Loading user comment form…