Search Results

Documents authored by Vahrenhold, Jan


Document
Teaching Support Systems for Formal Foundations of Computer Science (Dagstuhl Seminar 24251)

Authors: Tiffany Barnes, Jan Vahrenhold, Thomas Zeume, and Florian Schmalstieg

Published in: Dagstuhl Reports, Volume 14, Issue 6 (2024)


Abstract
Introductory courses on formal foundations of computer science - including basic courses on theoretical computer science (regular and context-free languages, computability theory, and complexity theory) as well as on logic in computer science (propositional and first-order logic, modeling, and algorithms for evaluation and satisfaction of formulas) - are a cornerstone of computer science curricula, yet many students struggle with their often theoretical contents. The recent influx of students in computer science, as well as the shift towards the inclusion of more online-based teaching ask for advanced teaching support systems that aid both students and instructors. This Dagstuhl Seminar focussed on fostering discussion between researchers in computing education, builders of systems for teaching formal foundations, as well as instructors of these foundations in order to facilitate more robust research and development of systems to support teaching and learning of the formal foundations of computer science.

Cite as

Tiffany Barnes, Jan Vahrenhold, Thomas Zeume, and Florian Schmalstieg. Teaching Support Systems for Formal Foundations of Computer Science (Dagstuhl Seminar 24251). In Dagstuhl Reports, Volume 14, Issue 6, pp. 108-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@Article{barnes_et_al:DagRep.14.6.108,
  author =	{Barnes, Tiffany and Vahrenhold, Jan and Zeume, Thomas and Schmalstieg, Florian},
  title =	{{Teaching Support Systems for Formal Foundations of Computer Science (Dagstuhl Seminar 24251)}},
  pages =	{108--129},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{6},
  editor =	{Barnes, Tiffany and Vahrenhold, Jan and Zeume, Thomas and Schmalstieg, Florian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.6.108},
  URN =		{urn:nbn:de:0030-drops-227301},
  doi =		{10.4230/DagRep.14.6.108},
  annote =	{Keywords: artificial intelligence in education, computing education research, educational data mining, formal foundations of computer science, intelligent tutoring systems, user modeling and adaptive personalization, user studies}
}
Document
Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues

Authors: Thore Thießen and Jan Vahrenhold

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)


Abstract
Oblivious RAM (ORAM) is a well-researched primitive to hide the memory access pattern of a RAM computation; it has a variety of applications in trusted computing, outsourced storage, and multiparty computation. In this paper, we study the so-called offline ORAM in which the sequence of memory access locations to be hidden is known in advance. Apart from their theoretical significance, offline ORAMs can be used to construct efficient oblivious algorithms. We obtain the first optimal offline ORAM with perfect security from oblivious priority queues via time-forward processing. For this, we present a simple construction of an oblivious priority queue with perfect security. Our construction achieves an asymptotically optimal (amortized) runtime of Θ(log N) per operation for a capacity of N elements and is of independent interest. Building on our construction, we additionally present efficient external-memory instantiations of our oblivious, perfectly-secure construction: For the cache-aware setting, we match the optimal I/O complexity of Θ(1/B log N/M) per operation (amortized), and for the cache-oblivious setting we achieve a near-optimal I/O complexity of O(1/B log N/M log log_M N) per operation (amortized).

Cite as

Thore Thießen and Jan Vahrenhold. Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{thieen_et_al:LIPIcs.ISAAC.2024.55,
  author =	{Thie{\ss}en, Thore and Vahrenhold, Jan},
  title =	{{Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.55},
  URN =		{urn:nbn:de:0030-drops-221832},
  doi =		{10.4230/LIPIcs.ISAAC.2024.55},
  annote =	{Keywords: offline ORAM, oblivious priority queue, perfect security, external memory algorithm, cache-oblivious algorithm}
}
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