January 27, 2011 11:30 PM Subscribe

I've been asked to teach a week at a summer university. Help me to design the most awesome computer science/discrete math course ever.

So I want to teach a class on graph theory/discrete math, but in a fun way. It's for comp sci with 1 year of background, not mathematicians. I want to link math with crime :-), like in Numb3rs.

This is what I've already half-prepared:

- First lecture: what is a graph, adjacency matrix, degrees, closeness, betweenness: Analysing 9/11 networks (Ata scores high in all those "scores", so my students will identify him)

- Last lecture: Networks and random graphs: Bioterrorism 101.

Everything in between is open.

I've already done some research (especially on Numb3rs), but most topics are either not very-well fleshed out, or too low-level. There are teaching resources by Texas Instruments, but they are rather infantile. Still, a starting point.

What I'm thinking about topic-wise (not neccessarily everything, not in that order..):

- Bipartite graphs, trees, spanning trees, breadth-first

- Matchings, marriage theorem

- directed graphs, TSP (For this, I probably use this idea: http://education.ti.com/xchange/US/Math/AlgebraII/7860/Act2_AntsGoMarching_EndofWatch_final.pdf)

- Euler, Hamilton

- Greedy-Algorithm

- Dijkstra (This will probably be a real-life example of a hijacked car - which route will they take? Also, there is this modified Dijkstra with DNA alignment, but I would have to research on that).

- MaxFlow

Ideas which involve some coding are okay. I do have time to research and create lesson plans. I do have motivation to do so. However, I do not have many ideas.

Thanks a lot!! :-)
posted by mathemagician to Education (7 answers total) 7 users marked this as a favorite

So I want to teach a class on graph theory/discrete math, but in a fun way. It's for comp sci with 1 year of background, not mathematicians. I want to link math with crime :-), like in Numb3rs.

This is what I've already half-prepared:

- First lecture: what is a graph, adjacency matrix, degrees, closeness, betweenness: Analysing 9/11 networks (Ata scores high in all those "scores", so my students will identify him)

- Last lecture: Networks and random graphs: Bioterrorism 101.

Everything in between is open.

I've already done some research (especially on Numb3rs), but most topics are either not very-well fleshed out, or too low-level. There are teaching resources by Texas Instruments, but they are rather infantile. Still, a starting point.

What I'm thinking about topic-wise (not neccessarily everything, not in that order..):

- Bipartite graphs, trees, spanning trees, breadth-first

- Matchings, marriage theorem

- directed graphs, TSP (For this, I probably use this idea: http://education.ti.com/xchange/US/Math/AlgebraII/7860/Act2_AntsGoMarching_EndofWatch_final.pdf)

- Euler, Hamilton

- Greedy-Algorithm

- Dijkstra (This will probably be a real-life example of a hijacked car - which route will they take? Also, there is this modified Dijkstra with DNA alignment, but I would have to research on that).

- MaxFlow

Ideas which involve some coding are okay. I do have time to research and create lesson plans. I do have motivation to do so. However, I do not have many ideas.

Thanks a lot!! :-)

I'm a math and code optimization person and I usually don't do "fluffy" stuff like iWhatever or SocialWhatever:-).

However, facebook and co could provide excellent data for network analysis.

posted by mathemagician at 2:07 AM on January 28, 2011

However, facebook and co could provide excellent data for network analysis.

posted by mathemagician at 2:07 AM on January 28, 2011

Spanning trees: working out how to dig a tunnel network to connect revolutionary cells

Matchings: deciding which members of the gang should carry out which tasks in a bank robbery, based on their various skills

Greedy algorithm: dividing up loot after the robbery

Sounds fun, I'll see if I can think up any more...

posted by d11 at 3:37 AM on January 28, 2011 [1 favorite]

Matchings: deciding which members of the gang should carry out which tasks in a bank robbery, based on their various skills

Greedy algorithm: dividing up loot after the robbery

Sounds fun, I'll see if I can think up any more...

posted by d11 at 3:37 AM on January 28, 2011 [1 favorite]

There's always using social networks to find connections between suspects. Person A and B are suspects but there's no obvious connection. Connectivity of their social/prison/Kevin Bacon networks gives information about possible paths between them (Menger's Theorem) and once it's discovered that there is low connectivity between A and B, the small group of people representing the vertex cut can be brought in for good cop-bad cop and someone gets jammed up. But maybe that's NYPD Blue.

posted by monkeymadness at 4:39 AM on January 28, 2011

posted by monkeymadness at 4:39 AM on January 28, 2011

Adding on d11's matchings idea, you can also plan how many you need on your crew with vertex colorings. Each job is a vertex, and if they conflict then there's an edge between them. The chromatic number of the graph is the minimum number of people you need to pull off the job.

This is fun. I'm teaching Graph Theory (hopefully) this Fall and look forward to stealing some of the ideas in this thread.

posted by monkeymadness at 4:41 AM on January 28, 2011 [1 favorite]

This is fun. I'm teaching Graph Theory (hopefully) this Fall and look forward to stealing some of the ideas in this thread.

posted by monkeymadness at 4:41 AM on January 28, 2011 [1 favorite]

Can you work in Prisoner's Dilemma in an interrogation scenario? Or is game theory out of scope?

posted by cross_impact at 11:46 AM on January 28, 2011

posted by cross_impact at 11:46 AM on January 28, 2011

As the lecturer, I can do whatever I want.

However, as a paedagoge, I need to give them a structure, some common topic, not random ideas. Else, I'd put loads of mathematical modelling and statistics and of, course, game theory into that, they link well with crime.

Thanks so far for the responses, I'm going to use them. :-)

posted by mathemagician at 11:09 PM on January 28, 2011

However, as a paedagoge, I need to give them a structure, some common topic, not random ideas. Else, I'd put loads of mathematical modelling and statistics and of, course, game theory into that, they link well with crime.

Thanks so far for the responses, I'm going to use them. :-)

posted by mathemagician at 11:09 PM on January 28, 2011

This thread is closed to new comments.

posted by XMLicious at 1:21 AM on January 28, 2011