Search Results

Documents authored by Vahrenhold, Jan


Document
Notional Machines and Programming Language Semantics in Education (Dagstuhl Seminar 19281)

Authors: Mark Guzdial, Shriram Krishnamurthi, Juha Sorva, and Jan Vahrenhold

Published in: Dagstuhl Reports, Volume 9, Issue 7 (2020)


Abstract
A formal semantics of a language serves many purposes. It can help debug the language's design, be used to prove type soundness, and guide optimizers to confirm that their work is correctness-preserving. Formal semantics are evaluated by several criteria: full abstraction, adequacy, soundness and completeness, faithfulness to an underlying implementation, and so on. Unfortunately, we know relatively little about how non-experts, such as students, actually employ a semantics. Which models are they able to grasp? How useful are these as they explain or debug programs? How does their use of models evolve with the kinds of programs they write? And does studying these kinds of questions yield any new insights into forms of semantics? This Dagstuhl Seminar intended to bridge this gap. It brought together representatives of the two communities-who usually travel in non-intersecting circles-to enable mutual understanding and cross-pollination. The Programming Languages community uses mathematics and focuses on formal results; the Computing Education Research community uses social science methods and focuses on the impact on humans. Neither is superior: both are needed to arrive at a comprehensive solution to creating tools for learning.

Cite as

Mark Guzdial, Shriram Krishnamurthi, Juha Sorva, and Jan Vahrenhold. Notional Machines and Programming Language Semantics in Education (Dagstuhl Seminar 19281). In Dagstuhl Reports, Volume 9, Issue 7, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{guzdial_et_al:DagRep.9.7.1,
  author =	{Guzdial, Mark and Krishnamurthi, Shriram and Sorva, Juha and Vahrenhold, Jan},
  title =	{{Notional Machines and Programming Language Semantics in Education (Dagstuhl Seminar 19281)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{7},
  editor =	{Guzdial, Mark and Krishnamurthi, Shriram and Sorva, Juha and Vahrenhold, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.7.1},
  URN =		{urn:nbn:de:0030-drops-116272},
  doi =		{10.4230/DagRep.9.7.1},
  annote =	{Keywords: computing education research, formal semantics, misconceptions, notional machines}
}
Document
Approximate Shortest Distances Among Smooth Obstacles in 3D

Authors: Christian Scheffer and Jan Vahrenhold

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)


Abstract
We consider the classic all-pairs-shortest-paths (APSP) problem in a three-dimensional environment where paths have to avoid a set of smooth obstacles whose surfaces are represented by discrete point sets with n sample points in total. We show that if the point sets represent epsilon-samples of the underlying surfaces, (1 ± O(sqrt{epsilon}))-approximations of the distances between all pairs of sample points can be computed in O(n^{5/2} log^2 n) time.

Cite as

Christian Scheffer and Jan Vahrenhold. Approximate Shortest Distances Among Smooth Obstacles in 3D. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{scheffer_et_al:LIPIcs.ISAAC.2016.60,
  author =	{Scheffer, Christian and Vahrenhold, Jan},
  title =	{{Approximate Shortest Distances Among Smooth Obstacles in 3D}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{60:1--60:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.60},
  URN =		{urn:nbn:de:0030-drops-68292},
  doi =		{10.4230/LIPIcs.ISAAC.2016.60},
  annote =	{Keywords: Geodesic distances; approximation algorithm; epsilon sample}
}
Document
Assessing Learning In Introductory Computer Science (Dagstuhl Seminar 16072)

Authors: Michael E. Caspersen, Kathi Fisler, and Jan Vahrenhold

Published in: Dagstuhl Reports, Volume 6, Issue 2 (2016)


Abstract
This seminar discussed educational outcomes for first-year (university-level) computer science. We explored which outcomes were widely shared across both countries and individual universities, best practices for assessing outcomes, and research projects that would significantly advance assessment of learning in computer science. We considered both technical and professional outcomes (some narrow and some broad) as well as how to create assessments that focused on individual learners. Several concrete research projects took shape during the seminar and are being pursued by some participants.

Cite as

Michael E. Caspersen, Kathi Fisler, and Jan Vahrenhold. Assessing Learning In Introductory Computer Science (Dagstuhl Seminar 16072). In Dagstuhl Reports, Volume 6, Issue 2, pp. 78-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{caspersen_et_al:DagRep.6.2.78,
  author =	{Caspersen, Michael E. and Fisler, Kathi and Vahrenhold, Jan},
  title =	{{Assessing Learning In Introductory Computer Science (Dagstuhl Seminar 16072)}},
  pages =	{78--96},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{2},
  editor =	{Caspersen, Michael E. and Fisler, Kathi and Vahrenhold, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.2.78},
  URN =		{urn:nbn:de:0030-drops-58899},
  doi =		{10.4230/DagRep.6.2.78},
  annote =	{Keywords: Assessment, Learning Objectives}
}
Document
In-Place Randomized Slope-Selection

Authors: Henrik Blunck and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)


Abstract
Slope selection is a well-known algorithmic tool used in the context of computing robust estimators for fitting a line to a collection $mathcal{P}$ of $n$ points in the plane. We demonstrate that it is possible to perform slope selection in expected $mathcal{O}(n log n)$ time using only constant extra space in addition to the space needed for representing the input. Our solution is based upon a space-efficient variant of Matouv{s}ek's randomized interpolation search, and we believe that the techniques developed in this paper will prove helpful in the design of space-efficient randomized algorithms using samples. To underline this, we also sketch how to compute the repeated median line estimator in an in-place setting.

Cite as

Henrik Blunck and Jan Vahrenhold. In-Place Randomized Slope-Selection. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{blunck_et_al:DagSemProc.06091.4,
  author =	{Blunck, Henrik and Vahrenhold, Jan},
  title =	{{In-Place Randomized Slope-Selection}},
  booktitle =	{Data Structures},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.4},
  URN =		{urn:nbn:de:0030-drops-8390},
  doi =		{10.4230/DagSemProc.06091.4},
  annote =	{Keywords: In-Place Algorithms, Slope Selection}
}
Document
A Simple Algorithm for I/O-efficiently Pruning Dense Spanners

Authors: Joachim Gudmundsson and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)


Abstract
Given a geometric graph $G=(S,E)$ in $R^d$ with constant dilation $t$, and a positive constant $\epsilon$, we show how to construct a $(1+\epsilon)$-spanner of $G$ with $O(|S|)$ edges using $O(sort(|E|))$ I/O operations.

Cite as

Joachim Gudmundsson and Jan Vahrenhold. A Simple Algorithm for I/O-efficiently Pruning Dense Spanners. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.04301.2,
  author =	{Gudmundsson, Joachim and Vahrenhold, Jan},
  title =	{{A Simple Algorithm for I/O-efficiently Pruning Dense Spanners}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.2},
  URN =		{urn:nbn:de:0030-drops-1566},
  doi =		{10.4230/DagSemProc.04301.2},
  annote =	{Keywords: No keywords}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail