Many students find that proof by induction is one of the most difficult topics in discrete mathematics. Even students who are able to write inductive proofs in a Discrete Mathematics course often find it difficult to write inductive proofs in Data Structures, Algorithms, Theory of Computation, and other computer science courses. Part of the reason for this is that discrete mathematics courses tend to emphasize weak induction over the natural numbers, but strong induction over recursively defined structures is much more useful in computer science.

With the support of a grant from the Sloan Foundation, nine computer scientists from liberal arts colleges came together in October, 1984 to form the Liberal Arts Computer Science Consortium (LACS) and to create a model curriculum appropriate for liberal arts colleges. Over the years the membership has grown and changed, but the focus has remained on helping to establish and maintain high-quality computer science programs in liberal arts colleges. In this report we discuss briefly the history of the group, the series of three curricula produced by LACS, and other contributions of the members to computer science education.

The 2004 school year marked significant changes in the Advanced Placement (AP) Computer Science curriculum. Most visibly, Java replaced C++ as the exam-testable programming language. More fundamentally, however, the AP CS curriculum now places a greater emphasis on object-oriented design than in previous years. Students are expected to be able to implement interfaces, design and implement class hierarchies using inheritance, analyze the tradeoffs between alternative designs and their associated efficiencies, and make use of Java Collection classes where appropriate. This special session is intended to inform both high school and college teachers as to the extent of these changes and how they affected the development and grading of the 2004 AP CS exams. In addition, it will provide practical insights as to how the new curriculum can be taught in high schools, and how teachers can better prepare their students for the exams.The AP CS Development Committee's charge is not only to provide a comprehensive testing mechanism, but also to recommend a direction that high school teachers should take in preparing a foundation for more advanced student studies during college. This special session will bring together two college and two high school members of the AP CS Development Committee to share some of their insights into the AP program.AP teachers will learn valuable information to continue to support their shift to Java in the classroom and about the exam for which they are preparing their students. College teachers will learn more about the AP CS curriculum and test development process, which may aid them in similar course redesigns and in the placement of students with AP credit.Time will be provided to discuss participant's questions.

With the Java language replacing C++ on the 2004 AP CS Exam, teachers need to be informed about the changes that must be implemented to support an OO approach to programming. This special session will include a retrospective look at the motivation behind the change to an object-oriented language, the process undertaken to select a testable language subset, the need to continue the development and classroom implementation of a Case Study, and a look at how the shift from an object-based approach to programming in C++ to an OO approach in Java leads to curriculum modification.The AP CS Development Committee's charge is to not only provide a comprehensive testing mechanism, but also advise, through various publications, a direction that high school teachers should take in preparing a foundation for more advanced student studies during college. This special session will bring together two college and two high school members of the AP CS Development Committee to share some of their insights into how the experts do it. Time will be provided to discuss participant's questions.

No abstract available.

Phenotypic analysis combined with molecular genetics is a powerful tool for mapping gene function onto the genome. Phenotypic data are, by their nature, descriptive, and as varied as the range of mutant phenotypes that can be presented by the organism under study. This paper discusses the mechanisms FlyBase has implemented to systematise published phenotypic data about Drosophila, and provides an introduction to the query tools available for the mining of the data. Though FlyBase is specific to Drosophila, the issues faced in devising protocols for capturing, storing and reporting data are the same issues faced by any database with an interest in using phenotypic data to maximise the potential of genomic analysis.

Sculptured surfaces used in automotive, aerospace and naval design are usually mathematically defined by parametric forms such as the well-known Bézier, B-Spline and nurbs representations. Although widely used in many applications, they are not ideal for NC tool path generation, primarily because of the difficulty in calculating gouge free contact points between the tool and the surface. Discrete representations of the parametric surfaces can be used to simplify the contact point calculation. Algorithms for surface discretization may be broadly classified as local, global or subdivision methods. Implementations of each of these classes were compared for five nurbs surfaces. An algorithm based on parametric rectangular subdivision produced the best overall performance.

We present a new method for testing compatibility of candidate edges in the greedy triangulation, and new results on the rank of edges in various triangulations. Our edge test requires O(1) time for test and update, O(n) space, and O(n) time to initialize. Based on these results, we present fast greedy triangulation algorithms with expected case running time of O(n log n) for uniform distributions over convex regions. While algorithms with O(n) expected case running times exist, the algorithms presented here are simpler to implement and work well in practice.

This paper presents an experimental comparison of a number of different algorithms for computing the Delaunay triangulation. The algorithms examined are: Dwyer's divide and conquer algorithm, Fortune's sweepline algorithm, several versions of the incremental algorithm (including one by Ohya, Iri and Murota, a new bucketing-based algorithm described in this paper, and Devillers's version of a Delaunay-tree based algorithm that appears in LEDA), an algorithm that incrementally adds a correct Delaunay triangle adjacent to a current triangle in a manner similar to gift wrapping algorithms for convex hulls, and Barber's convex hull based algorithm. Most of the algorithms examined are designed for good performance on uniformly distributed sites. However, we also test implementations of these algorithms on a number of non-uniform distributions. The experiments go beyond measuring total running time, which tends to be machine-dependent. We also analyze the major high-level primitives that algorithms use and do an experimental analysis of how often implementations of these algorithms perform each operation.

This paper presents an experimental comparison of a number of different algorithms for computing the Deluanay triangulation. The algorithms examined are: Dwyer’s divide and conquer algorithm, Fortune’s sweepline algorithm, several versions of the incremental algorithm (including one by Ohya, Iri, and Murota, a new bucketing-based algorithm described in this paper, and Devillers’s version of a Delaunay-tree based algorithm that appears in LEDA), an algorithm that incrementally adds a correct Delaunay triangle adjacent to a current triangle in a manner similar to gift wrapping algorithms for convex hulls, and Barber’s convex hull based algorithm. Most of the algorithms examined are designed for good performance on uniformly distributed sites. However, we also test implementations of these algorithms on a number of non-uniform distibutions. The experiments go beyond measuring total running time, which tends to be machine-dependent. We also analyze the major high-level primitives that algorithms use and do an experimental analysis of how often implementations of these algorithms perform each operation.

Article Free Access Share on Fast greedy triangulation algorithms Authors: Matthew T. Dickerson Department of Mathematics and Computer Science, Middlebury College, Middlebury VT Department of Mathematics and Computer Science, Middlebury College, Middlebury VTView Profile , Robert L. Scot Drysdale Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH Department of Mathematics and Computer Science, Dartmouth College, Hanover, NHView Profile , Scott A. McElfresh Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH Department of Mathematics and Computer Science, Dartmouth College, Hanover, NHView Profile , Emo Welzl Institut für Informatik, Freie Universität Berlin Institut für Informatik, Freie Universität BerlinView Profile Authors Info & Claims SCG '94: Proceedings of the tenth annual symposium on Computational geometryJune 1994Pages 211–220https://doi.org/10.1145/177424.177649Published:10 June 1994Publication History 18citation883DownloadsMetricsTotal Citations18Total Downloads883Last 12 Months55Last 6 weeks12 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Enumerating k distances for n points in the plane Authors: Matthew T. Dickerson Department of Mathematics and Computer Science, Middlebury College Department of Mathematics and Computer Science, Middlebury CollegeView Profile , R. L. Scot Drysdale Department of Mathematics and Computer Science, Dartmouth College Department of Mathematics and Computer Science, Dartmouth CollegeView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 234–238https://doi.org/10.1145/109648.109674Online:01 June 1991Publication History 10citation269DownloadsMetricsTotal Citations10Total Downloads269Last 12 Months14Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free AccessMultiplicatively weighted crystal growth Voronoi diagrams (extended abstract) Share on Authors: Barry F. Schaudt Dartmouth College, Dept. of Math and Computer Science, Hanover NH Dartmouth College, Dept. of Math and Computer Science, Hanover NHView Profile , R. L. Scot Drysdale Dartmouth College, Dept. of Math and Computer Science, Hanover NH Dartmouth College, Dept. of Math and Computer Science, Hanover NHView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 214–223https://doi.org/10.1145/109648.109672Online:01 June 1991Publication History 9citation523DownloadsMetricsTotal Citations9Total Downloads523Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe a method for simulating and verifying the correctness of Numerical Control (NC) programs. NC programs contain the sequence of cutting tool movements which machine raw stock into a finished object. Our method is based on a discrete approximation of the object by a set of points. A vector is passed through each of the points and machining is simulated by finding the intersections of tool movements with these vectors. We present a point-selection method and an analysis that shows that the error introduced by the approximation can be made as small as desired. The run time is inversely proportional to the allowable error and the size of the cutting tool, and directly proportional to the distance that the cutting tool moves.

We consider the following problem: Given a rectangle containing N points, find the largest area subrectangle with sides parallel to those of the original rectangle which contains none of the given points. If the rectangle is a piece of fabric or sheet metal and the points are flaws, this problem is finding the largest-area rectangular piece which can be salvaged. A previously known result [13] takes $O(N^2 )$ worst-case and $O(N\log ^2 N)$ expected time. This paper presents an $O(N\log ^3 N)$ time, $O(N\log N)$ space algorithm to solve this problem. It uses a divide-and-conquer approach similar to the ones used by Bentley [1] and introduces a new notion of Voronoi diagram along with a method for efficient computation of certain functions over paths of a tree.

We present an “expanding waves” view of Voronoi diagrams that allows such diagrams to be defined for very general metrics and for distance measures that do not qualify as metrics. If a pebble is dropped into a still pond, circular waves move out from the point of impact. If n pebbles are dropped simultaneously, the places where wave fronts meet define the Voronoi diagram on the n points of impact.

Given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time $O(kn\lg n + n\lg ^2 n)$. For the special case $k = 3$ we give $O(n\lg n)$ algorithms for these problems. Several related issues are discussed.

Given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time O(knlg n + n lg 2n). For the special case k = 3 we give O (nlgn) algorithms for these problems. Several related issues are discussed.

In this paper we study the Voronoi diagram for a set of N line segments and circles in the Euclidean plane. The diagram is a generalization of the Voronoi diagram for a set of points in the plane and has applications in wire layout, facility location, clustering and contouring problems. We present an $O(N(\log N)^2 )$ algorithm for constructing the diagram. It is an improvement of a previous known result which takes $O(Nc^{\sqrt {\log N} } )$ time. The algorithm described in this paper is also shown to be applicable under a more general metric if certain conditions are satisfied.

This paper develops sorting networks using the divide/sort/merge strategy. These networks require \[ (0.25)N( \log _2 N )^2 - (0.386)N( \log _2 N ) + O(N) \] comparison-interchanges to sort a list of length N. This is an improvement of order $N(\log _2 N)$ over the best networks previously reported. (Using different methods, Van Voorhis [8] has improved upon these results.)