We use cache-sensitive memory layouts to improve search performance in ordinary binary search trees, without increasing the time complexity of insertion or deletion. Our approach does not require changes to the structure of the nodes or the rebalancing strategy of the tree. Cache-sensitivity is maintained with a memory-layout invariant that keeps a given number of neighboring nodes in the tree stored in the same cache block. We show how to preserve it using worst-case constant-time operations executed when the tree changes. In our extensive experiments, the invariant consistently improved the search performance of large AVL and red–black trees by 26–32%, on synthetic data as well as realistic search tree operations extracted from a database benchmark. We also compare binary search trees with several cache-sensitive B-trees, and non-dynamic approaches for laying out tree nodes in a multi-level memory hierarchy.

We consider online bulk-delete operations on a large database table organized as a primary (sparse) B+-tree index on a multi-attribute key. Using the natural range partitions induced by prefixes of the key, we define a multi-granular key-range locking protocol in which a bulk operation locks a small number of logical fragments of the table covering the target of the operation. We also present an efficient and recoverable bulk-delete algorithm that minimizes the work needed in B-tree rebalancing and in transaction rollback. All the locks needed for a bulk-delete operation are acquired during a scan of the leaf pages covering the target key range; in this scan the records qualifying for deletion are only marked as deleted. The records are physically deleted in a rebalance phase that avoids visiting subtrees in which all records qualify for deletion, thus saving considerably on the number of rebalancing operations.

In this paper, we present some experiences on using automatic assessment in large scale courses of introductory programming, data structures, and algorithms over a period of 10 years. Automatic assessment provides an effective method for giving immediate 24/7 feedback service for students of mass courses. A very important factor in the promoting of learning is the possibility to resubmit answers after receiving the feedback. However, our experience shows that the resubmission option is not the only key motivation factor. More important factors include the challenge of exercises and the grading scale or the course assignments. A successful combination of all of these can produce good learning results.

No abstract available.

Automatic assessment of programming exercises has become an important method for grading students' exercises and giving feedback for them in mass courses. We describe a system called Scheme-robo, which has been designed for assessing programming exercises written in the functional programming language Scheme. The system assesses individual procedures instead of complete programs. In addition to checking the correctness of students' solutions the system provides many different tools for analysing other things in the program like its structure and running time, and possible plagiarism. The system has been in production use on our introductory programming course with some 300 students for two years with good results.