David Eppstein - Publications

Educational assessment

• Choosing subsets with maximum weighted average.
  D. Eppstein and D. S. Hirschberg.
  Tech. Rep. 95-12, ICS, UCI, 1995.
  5th MSI Worksh. on Computational Geometry, 1995, pp. 7–8.
  J. Algorithms 24: 177–193, 1997.

  Uses geometric optimization techniques to find, among n weighted values, the k to drop so as to maximize the weighted average of the remaining values. The feasibility test for the corresponding decision problem involves k-sets in a dual line arrangement.

  (Full paper)

• Upright-quad drawing of \(st\)-planar learning spaces.
  D. Eppstein.
  arXiv:cs.CG/0607094.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 282–293.
  J. Graph Algorithms and Applications 12 (1): 51–72, 2008 (special issue for GD'06).

  We consider graph drawing algorithms for learning spaces, a type of \(st\)-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any \(st\)-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an \(st\)-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.

  (GD'06 talk slides)

• Learning sequences.
  D. Eppstein.
  arXiv:0803.4030.
  

  How to implement an antimatroid, with applications in computerized education.

• Combinatorial pair testing: distinguishing workers from slackers.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  arXiv:1305.0110.
  13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario.
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 316–327.
  

  We study the problem of distinguishing workers (people who complete their assigned tasks) from slackers (people who do not contribute towards the completion of their tasks) by grouping people in pairs and assigning a task to each group.

• Knowledge Spaces: Applications in Education.
  J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
  Springer, 2013.

  This edited volume collects experiences with automated learning systems based on the theory of knowledge spaces, and mathematical explorations of the theory of knowledge spaces and their efficient implementation.

• Learning sequences: an efficient data structure for learning spaces.
  D. Eppstein.
  In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
  Springer, 2013, pp. 287–304.

  We show how to represent a learning space by a small family of learning sequences, orderings of the items in a learning sequence that are consistent with their prerequisite relations. This representation allows for the rapid generation of the family of all consistent knowledge states and the efficient assessment of the state of knowledge of a human learner.

• Projection, decomposition, and adaption of learning spaces.
  D. Eppstein.
  In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
  Springer, 2013, pp. 305–322.

  In another chapter of the same book we used learning sequences to represent learning spaces and perform efficient knowledge assessment of a human learning. In this chapter we show how to use the same data structure to build learning spaces on a sample of the items of a larger learning space (an important subroutine in knowledge assessment) and to modify a learning space to more accurately model students.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.