Dinesh Mehta
ABSTRACT
The matching problem in bipartite graphs is the basis for many applications that have become especially prominent with the advent of online markets that connect two entities (e.g., job-seekers and employers). Its algorithmic basis is the max-flow problem in networks, a topic that is often covered in introductory algorithms texts and courses.
Separately, the Computer Science education literature is abundant with examples which indicate that the quality of the experience in the implementation of programming tasks is enhanced when done in groups.
In this paper, we describe the application of a network-flow-based matching algorithm in bipartite graphs to form project groups in the algorithms course at the Colorado School of Mines (CSM). This activity simultaneously provides students with an immersive experience in a bipartite matching application. We present a small exploratory study on the effectiveness of the activity.
- L. Barker and J. M. Cohoon. Key Practices for Retaining Undergraduates in Computing. http://www.ncwit.org, Sept. 2009.Google Scholar
- J. Brown and G. Dobbie. Supporting and evaluating team dynamics in group projects. In The proceedings of the 30th SIGCSE technical symposium on Computer science education, SIGCSE '99, pages 281--285, 1999. Google ScholarDigital Library
- L. Cassel, A. Clements, G. Davies, M. Guzdial, R. McCauley, A. McGettrick, B. Sloan, L. Snyder, P. Tymann, and B. Weide. Computer Science Curriculum 2008: An Interim Revision of CS 2001. http://www.acm.org/education/curricula.html, 2008.Google Scholar
- C. Christodoulopoulos and K. Papanikolaou. A group formation tool in an e-learning context. In Proc. 19th IEEE International Conference on Tools with Artificial Intelligence, Oct. 2007. Google ScholarDigital Library
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, Cambridge, Massachussetts, third edition, 2009. Google ScholarDigital Library
- K. Deibel. Team formation methods for increasing interaction during in-class group work. In Proceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education, ITiCSE '05, pages 291--295, 2005. Google ScholarDigital Library
- A. Diwan, W. M. Waite, and M. H. Jackson. An infrastructure for teaching skills for group decision making and problem solving in programming projects. In Proceedings of the 33rd SIGCSE technical symposium on Computer science education, SIGCSE '02, pages 276--280, 2002. Google ScholarDigital Library
- D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010. Google ScholarDigital Library
- D. Gusfield and R. Irving. The Stable Marriage Problem. The MIT Press, 1989. Google ScholarDigital Library
- D. Johnson, R. Johnson, and K. Smith. Active Learning: Cooperation in the college classroom. Interaction Book Company, 1991.Google Scholar
- A. Joseph and M. Payne. Group dynamics and collaborative group performance. In Proceedings of the 34th SIGCSE technical symposium on Computer science education, SIGCSE '03, pages 368--371, 2003. Google ScholarDigital Library
- N. Katira, L. Williams, E. Wiebe, C. Miller, S. Balik, and E. Gehringer. On understanding compatibility of student pair programmers. In Proceedings of the 35th SIGCSE technical symposium on Computer science education, SIGCSE '04, pages 7--11, 2004. Google ScholarDigital Library
- J. Kleinberg and E. Tardos. Algorithm Design. Pearson, 2006. Google ScholarDigital Library
- Y.-T. Lin, Y.-M. Huang, and S.-C. Cheng. An automatic group composition system for composing collaborative learning groups using enhanced particle swarm optimization. Computers & Education, 55:1483--1493, 2010. Google ScholarDigital Library
- H. Simon. Models of Man. John Wiley, 1957.Google ScholarCross Ref
- D. Smarkusky, R. Dempsey, J. Ludka, and F. de Quillettes. Enhancing team knowledge: instruction vs. experience. In Proceedings of the 36th SIGCSE technical symposium on Computer science education, SIGCSE '05, pages 460--464, 2005. Google ScholarDigital Library
- W. M. Waite, M. H. Jackson, A. Diwan, and P. M. Leonardi. Student culture vs group work in computer science. In Proceedings of the 35th SIGCSE technical symposium on Computer science education, SIGCSE '04, pages 12--16, 2004. Google ScholarDigital Library
- D.-Y. Wang, S. Lin, and C.-T. Sun. Diana: A computer-supported heterogeneous grouping system for teachers to conduct successful small learning groups. Computers in Human Behavior, 23:1997--2010, 2007. Google ScholarDigital Library
Index Terms
- Forming project groups while learning about matching and network flows in algorithms
Recommendations
Maximum weight induced matching in some subclasses of bipartite graphs
AbstractA subset of edges of a graph is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is the same as G[S], the subgraph of G induced ...
Acyclic Matching in Some Subclasses of Graphs
Combinatorial AlgorithmsAbstractA subset of edges of a graph is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called an acyclic matching if G[V(M)], the subgraph of G induced by the M-saturated vertices of G is acyclic. The Acyclic ...
Dominating induced matching in some subclasses of bipartite graphs
AbstractA subset M ⊆ E of edges of a graph G = ( V , E ) is called a matching if no two edges of M share a common vertex. An edge e ∈ E is said to dominate itself and all other edges adjacent to it. A matching M in a graph G = ( V , E ) is ...
Comments