As professors, we want the students in our classes to succeed in mastering the material that we set out to teach them, but we must balance this desire with the knowledge that we have other responsibilities and a limited number of hours in the day. In this report, we document our implementation of a mastery learning inspired pedagogy using specifications grading in a software engineering course from the spring semester of 2022 in which 142 students were enrolled. Our two main goals with this approach were to reduce the administrative burden of the class with respect to grading and to promote mastery of course material while maintaining academic rigor. We provide evidence that both of these goals were at least partially achieved. In addition to outlining the structure of the course, we identify several areas where there is room for improvement with this approach and provide an overview of an online application we developed to facilitate the course.

This paper presents a case study detailing our experience applying a combination of Mastery Learning and Specs Grading to a section of a Discrete Mathematics course with 128 students. Our principle reason to use this pedagogy was to improve the learning outcomes of our students, so all students would have a good chance of succeeding, regardless of their previous experience. The course was focused on 10 main skill areas. Each week a new skill area was introduced and a quiz for that skill area was provided that week and each week thereafter. The quizzes were graded pass/fail, either they demonstrated complete mastery or they did not. Students who demonstrated mastery were no longer required to take the quizzes on that skill area in later weeks. The amount of extra work required for this approach with regards to grading was roughly twice as much as would have been required with a traditional midterm/final exam structure and three times as much for creating quiz questions. Despite this increase in the number of items that required grading, the overall time spent grading was greatly reduced due to the use of pass/fail grading. The Mastery Learning approach provided a strong incentive for students to attempt to master all of the core skill areas. By the end of the semester, 75% of the students had mastered at least nine of the ten skill areas. In this paper we discuss this approach and its implications for CS courses more generally.

In this lightning talk, we explore the impact of adding reflective debugging to a web-based problem-solving IDE, Spinoza, that we created to support teaching programming with Python. Spinoza allows the instructor to create (or select from a library) Python problems with automatic unit tests. Each time a student attempts a new problem, the system randomly decides if reflective debugging will be required; in which case each time the student runs their code and the code does not pass the unit tests, the student will be required to classify the type of error (syntax, logic or runtime error), provide a description of the bug, and explain how they plan to fix it before they are allowed to revise and run the code again. Our main result from this pilot study is that the number of debugging steps to reach a correct solution was statistically significantly less when students were required to use reflective debugging. Our hope was that by being required to analyze each error for some problems (about one out of three), students would see the benefits and develop the habit of reflective debugging even when it was not required.

Financial knowledge has a tangible impact on an individual’s ability to make positive financial decisions in their life. It has been estimated that the difference between the 75th and 25th percentile of the financial literacy index is equivalent to approximately an 80,000 euro difference in net worth and has significant impact on financial decisions made throughout one’s working life and into retirement. The need for quality financial education is clear, but many studies show that personal finance classes offered today do not seem to have significant impact on the financial literacy of the students who take them. One hypothesis of this paper is that traditional instruction methods, which do not force students to exercise the financial tools they need to be fluent with as adults, hinder their ability to improve their financial literacy. We also argue that analysis of game interactions may be a more effective assessment mechanism than traditional academic tests. There is a growing body of evidence that the immersive elements of particular styles of games can have a significant impact on learning outcomes. This paper offers a potential starting point from which an immersive game, which leverages real world financial decision-making as its main mechanic, can be born. We will discuss the underlying design of such a game and how it lays the foundation for a game that could achieve financial literacy outcomes. Such outcomes would empower students with the skills to make positive financial choices in their lives and better achieve personal financial goals.

In this paper we introduce the notion of Recursive Pedagogy, which is a computer-supported approach to teaching and learning in which students solve problems assigned by an instructor using a Problem Solving Learning Environment, and their attempts to solve that problem are then used by the system to create new kinds of problems to help them build high level cognitive skills. The Recursive Pedagogy approach generalizes an approach we introduced earlier: the Solve-Then-Debug (STD) pedagogy to teach coding. In STD, students write a program given its description and, when their code passes all of the unit tests, they debug a sequence of incorrect programs submitted by their peers, starting with those with the most common errors. In this paper, we discuss two new Recursive Pedagogies that we have implemented in the Spinoza Python Tutor: Solve-Then-Critique-Correct-Solutions shows students correct programs from their peers and asks them to critique the code relative to a rubric; Solve-Then-Analyze-Unit-Tests shows students results of a set of unit tests and asks them to describe the probable error based on the unit test results. After students submit their Recursive Pedagogy analysis of a peer’s attempt, they are shown other students’ analyses of that attempt and are asked to select the best one. Recursive Pedagogies are designed to build skills in problem-solving, debugging, testing, and composing high quality solutions. Moreover, they can be used in a flipped class and they keep all students engaged in either problem solving or one of the other skills.

This Innovative Practice Full Paper reports on a pilot study of our 3D game that was designed to teach students introductory concepts in security and cryptography. Game based learning and serious games are getting attention for their potential effect on increasing learner enjoyment and understanding of educational concepts and skills. The game we discuss here is a version of the “Escape the Room” puzzles where the player needs to find and solve a sequence of problems to escape from a room. Students must guide their avatar around a room containing a computer, a trash can, a locked door, and other objects. When they approach an object they are allowed to interact with it in various ways which provides clues and challenges that can only be solved with an understanding of certain cryptographic concepts. This game was tested with a group of 16 students, the students were asked to fill a pre-test and post-test survey about their experience with games, their demographics, and their understanding of certain cryptography concepts. A paired t-test shows a significant increase in understanding of cryptographic concepts among the students after playing the game, this increase in learning was independent of their gender and almost all of the students enjoyed the experience of learning in a game-based way.

This Innovative Practice Full Paper presents our work on using machine learning to estimate student mastery of Calculus skills based on their performance using an online Problem Solving Learning Environment. We have shown in earlier papers that we can make accurate predictions of student performance at an aggregate level using the Performance Factors Analysis (PFA) approach. We had an expert teacher label 243 Calculus problems with the skills required to solve each problem and then use PFA to predict student performance using a dataset with 1609 students. In this paper, we improved our labeling of the skills by adding new difficulty tags as well as showing how to apply interactive machine learning to help the expert teacher improve their labeling of the skills required for each problem. This can then improve the prediction accuracy for future classes doing the same problems. It can also help the expert teacher improve the definition of the skills to make them more effective features for predicting student performance. The technique we present is to use a human-in-the-loop hill climbing process where a skill is added or removed, and we test to see whether this significantly improves the predictions for that problem over all students. If so, then the instructor is asked to verify whether indeed that particular skill should be removed or added. The new skill could be the result of the expert making a mistake in labelling a problem with skills, but it could also suggest that a modification of the skill definition would yield more accurate predictions. The key idea behind this approach is to harness the strengths of both the instructor and the machine learning algorithms to improve the effectiveness of the pedagogical system.

There has been a rapid proliferation of auto-graders for introductory programming courses to cope with rapidly expanding Computer Science enrollments. In this poster we report on our research in developing and deploying a problem solving learning environment, Spinoza 3.0, which goes beyond auto-grading and provides active learning exercises to teach debugging, testing, and good coding style in addition to providing immediate feedback on program correctness. The key idea is to collect all of the attempts by all students to a particular problem generated by a particular class and to form them into equivalence classes where two attempts are equivalent if they produce exactly the same values on all of the unit tests. This allows the system to find the most common errors made by that class. The system then generates a variety of different kinds of problems by selecting either one of the most common errors or one of the correct solutions and asking the students to critique it. After a student makes a critique they are shown (a subset of) the critiques of their fellow students and are asked to pick the best one before proceeding to the next problem. Since the system generates new problems precisely tailored to this particular class, by turning selected attempts into new problems, we call this approach Recursive Pedagogy. This poster reports on preliminary results we have obtained using Recursive Pedagogy in an Introduction to Python Programming course with 19 college students.

This Innovative Practice paper presents a new approach to monitoring the performance of students working in web-based Problem Solving Learning Environments (PSLEs) which can be used to introduce active learning in large classes. This approach allows the instructor to pose a problem that all students will immediately attempt to solve. Classroom orchestration tools allow the instructor to monitor, in detail, the progress of the class on that problem. The Problem Solving Markov Model (PSMM) is one such orchestration tool. It provides a real-time graphical view of all equivalence classes of attempts that students have made on a particular problem and it shows the probabilities of going from one incorrect attempt to another. In this paper, we describe the PSMM for a particular PSLE for coding, called Spinoza, and we explore the connection between PSMM equivalence classes and student misconceptions. We also introduce an extension of the PSMM which allows the instructor to zoom in and out of the time dimension and we discuss the pedagogical applications of this extension for orchestration in large classes.

In this Innovative Practice, Work-in-Progress paper we present a new version of our web-based problem solving learning environment called CalcTutor. The key feature of the new CalcTutor system is that it organizes Mathematics problems based on the skills that they require and uses a machine learning technique (Performance Factors Analysis) to provide a difficulty estimate for each problem, personalized for each student in the system. This facility allows students to effectively engage in self- study by searching the library for problems that require specified skills. It ranks the problems found in the search by their difficulty for that particular student (the probability the student will solve them correctly on the first attempt). The current version of CalcTutor makes creating problems easy as well. It provides a simple and powerful question authoring tool which allows teachers to build both multiple choice questions and questions where the answers are mathematical functions of one variable.

In this Innovative Practice Full Paper, we examined whether signals from inexpensive, wearable brainwave sensors could be used to identify the STEM learning task in which a student was engaged. Twelve subjects completed four different STEM learning tasks - two entailing passive learning (watching a video or reading), and two entailing active learning (solving problems based on the passive learning). There were two mathematics tasks (one active and one passive) and two Python programming tasks (one active, one passive). Subjects were fitted with wearable brainwave sensors that captured cortical oscillations from four scalp electrodes, and transformed the signals from each electrode into five distinct frequency bands. This yielded 10 samples per second within each frequency band and from each electrode. We then trained ensemble-based machine learning algorithms (boosting and bagging of decision tree learners) to classify various features of tasks and subjects from a single sample of brainwave activity. We explored several different types of training/testing regimes, and our results suggest that within a single session, brain activity patterns for each of these four types of learning are substantially different, but that the patterns do not generalize well between sessions. Importantly, the brainwave patterns differ greatly between individuals, which suggests that applications using such devices will need to rely on personalization to achieve high accuracy. The project is a first step toward developing apps that could use individualized EEG feedback to help subjects develop learning strategies that optimize their learning experience.

Enrollments in Computer Science classes have been increasing at an exponential rate in many colleges and universities, which has resulted in a rapid increase in class size especially for the Introduction to Programming classes. The Spinoza system was developed as a way to add active learning to very large CS1 classes taught in Python. The main goals were to keep all students actively involved in learning how to code and how to debug. The key innovation of Spinoza is the Solve-Then-Debug activity in which students first solve a problem by getting their code to pass a suite of unit tests and then they debug the most common incorrect attempts of their classmates. The instructor has access to a wide variety of tools for viewing performance of the class and the individual students in real-time. In this demo, we will show you how to use Spinoza in your own classes. In particular, we show how to create a class, create a problem, and how to monitor the progress of the students in both the solving and the crowdsourced debugging phase, and how to use the other orchestration features to effectively explore the concepts exposed by that problem.

In this paper we present a new approach to flipping large introductory programming classes that we call the Solve-Then-Debug approach. This is a Computer Supported Agile Teaching methodology in which students solve problems using a web-based IDE we created, Spinoza, and then start reviewing failed attempts by their peers to classify the errors and comment on them. The classification and comment information is then made available as a hint to those students still trying to solve the problem when they encounter a similar error. Spinoza provides a wide variety of visualizations and dashboards that allow the instructor to closely monitor the progress of the students in this activity and to pivot to another phase of the activity at the appropriate time. It also has features that allow the instructor to easily detect and intervene with students who have failed to demonstrate mastery of the skills and concepts covered in that lesson. Spinoza builds on the ideas behind several other recent systems and this paper demonstrates that the Solve-Then-Debug approach can successfully keep all students actively engaged in learning coding skills even when there is a large range of skills in the class.

Automatic grading systems, such as WebWork, are becoming much more widely used as they relieve the instructor from needing to grade student work, provide students with automatic feedback, and can allow for immediate resubmission. They have also been shown to improve the effectiveness of teaching and learning. In this paper, we apply Item Response Theory (IRT) to a large WebWork Calculus homework dataset to provide a skill level for each student and item characteristics curves for each problem which we then show accurately predict the probability a given student will get a particular problem correct. A student's skill level at the end of a course represents a kind of summative assessment which can be used to accurately predict how well they would answer future questions, and hence is perhaps a better indicator of subject mastery than the grade on the final exam. We also apply the Performance Factors Analysis (PFA) approach to our data and use it to provide a more fine-grained analysis of the student's mastery. PFA requires labeling each problem with a set of skills that are required to solve that problem. It produces a formula that accurately predicts the probability that students will correctly answer a new question based on their previous answers. We use the PFA approach to produce a dashboard for every student which isolates their mastery of different skills. Our dataset consisted of 703,743 attempted solutions to 243 different questions by 1609 students in 87 sections of Calculus I at a large university. Both the IRT and PFA approaches produced accurate predictions, and PFA enabled a dashboard to be constructed for each of the students.

In this paper we introduce new tools for measuring and visualizing the learning process of students in large classes where students are required to use a computer-supported problem solving learning environment (PSLE) either in class or as homework. These learning environments give students unlimited opportunities to propose a solution to the problem and give them immediate feedback. We show how to create a graphical representation, the Problem Solving Markov Model (PSMM), of the set of all attempted solutions proposed by the class. Each node in the PSMM consists of an equivalence class of attempted solutions and each edge corresponds to a transition from one attempted solution to another in one step. The edges are typically labeled with the number of times a students went directly from one attempted solution to the next, or with the probability of going between the two nodes. We give examples from two tools: CalcTutor for Calculus problems, and Spinoza for Java or Python programming, and we provide several pedagogical applications of PSMMs which give the instructor a simple way to obtain a highly nuanced understanding of mastery of the problem solving process for individual students and for the class as a whole.

This paper proposes a simple method to add optional live-streaming to a highly interactive class in a way that reduces the number of students physically present in the classroom and doesn't hurt student performance. The effect of allowing live-streaming was analyzed by running an experiment where partway through the semester students in a flipped advanced level Computer Graphics class were given the option to attend the class remotely using a live-stream of the class with required use of a multi-featured audience response system (TeachBack). The results show that allowing remote attendance with TeachBack decreased the number of students attending physically from 93% to 75% of registered students and had no effect on unexcused absences. Students believed that their remote attendance was just as effective for their learning as attending classes face-to-face and analysis of the data confirmed their beliefs; they did however generally prefer being physically present in class. Our results suggest that appropriate use of live-streaming coupled with an Audience Response System can reduce some of the demand for large lecture halls by allowing a self-selected subset of students to attend some or all of the classes remotely. A large percentage of the students in the class felt that a live-streaming option should be added to most classes and this paper demonstrates that this goal is feasible and pedagogically justifiable.

We have designed and built CalcTutor, an online educational tool for Calculus that employs the Teachers Dilemma methodology. This methodology is centered around a game framework where students take on, and are rewarded for playing well, both the role of learner and teacher. Students create machine-verifiable questions for each other and gain points based on not only correct answers but also asking good questions. This framework has been used and studied in a variety of projects, mostly in the K-12 arena. The CalcTutor tool expands this approach to college level classes, specifically introductory Calculus. In this paper, we are reporting on our experience with a pilot study of CalcTutor, as used in conjunction with a college Calculus class. The system is designed to support learning in two ways, teachers can build quizzes for their students and the students can pair off and play games with each other. The students are given dynamic feedback about how appropriate their question is for their partner in the game as they develop each problem. During this pilot study, students asked and answered problems of two types: finding the derivative of a function and calculating the tangent line to a function at a point. The system was simultaneously tested in five introductory Calculus sections which generated a sizeable body of system data as well as survey feedback. Unfortunately, like many new tools, some of the students found getting used to the interface hard and some of our theoretical concepts did not pan out. Nevertheless the technical parts of the system worked well; students and teachers were able to create and answer questions without any issues. Some of the untested ideas that we were trying out met with success. And many students enjoyed some features of the system, particularly the instantaneous feedback.

This paper describes three years of experience with an intensive three course summer semester on web and mobile entrepreneurship for second year CS students and beyond. The program is similar in structure to a high school summer camp or to a summer accelerator/incubator program except that it has a much higher level of academic content and provides the credit equivalent to three Computer Science electives and a full semester of residency. The program has been effective at teaching students production programming and entrepreneurship and has stimulated entrepreneurial activity during the academic year. It is taken by about half of the CS majors in the department which is surprising since it requires them to spend their summer months in a very intense academic and entrepreneurial experience which is quite different from the usual summer experience of their peers.

The thesis of this paper is that Scheme-based web programming is a worthy organizing topic for CS0 computer literacy courses. We describe an approach to introducing non-science majors to Computer Science by teaching them to write webpages using HTML and CSS and to also write applets and servlets using Scheme. The programming component of our approach is completed in about nine weeks of a thirteen week course, leaving time for a treatment of more traditional CS0 topics such as intellectual property, privacy, artificial intelligence, the limits of computability, PC architecture, Operating Systems, CMOS and logic circuits. We argue that the use of a high level scripting language (like Scheme) is essential to the success of this approach. We also argue that wide scale success in teaching web programming to non-majors could enhance the students productivity when they enter the job market, and hence this approach deserves further study.

We describe an approach to introducing non-science majors to programming and computation in part by teaching them applets, servlets, and groupware applications. The course uses a dialect of didactic Scheme that is implemented in, and tightly integrated with, Java. The declarative nature of our approach allows non-science majors with no programming background to develop surprisingly complex web applications in about half a semester. This level of programming provides a context for a deeper understanding of computation than is usually feasible in a Computer Literacy course.

Computer Science as an academic discipline should be guided not only by the "state of the art", but also by the "state of the practice"[1]. Over the last few years, Internet/Web has been undeniably the most "high profile" practice of computing. Yet, Computer Science curricula across the country have not kept up with this development - not many schools are offering courses, concentrations and/or majors that identify the Internet/Web as the central principle, and address its issues and needs.In this panel, the panelists will share their experience designing courses and concentrations to address this need, and present their vision for what an Internet-related Curriculum should include: the courses, the technologies, and the overarching themes. The viewpoints presented here are quite diverse: arguing in favor of Internet-related coursework for majors versus non-majors, as a course/minor/major, as an across-the-curriculum theme, as an interdisciplinary endeavor, as an introductory course versus a capstone course, and from the points of view of a community college, four-year institutions and a graduate institution. We hope that these diverse viewpoints will foster vigorous discussion at the panel about the place of Internet-Computing in the Computer Science curriculum, and its design.

We start with a mathematical definition of a real interval as a closed, connected set of reals. Interval arithmetic operations (addition, subtraction, multiplication, and division) are likewise defined mathematically and we provide algorithms for computing these operations assuming exact real arithmetic. Next, we define interval arithmetic operations on intervals with IEEE 754 floating point endpoints to be sound and optimal approximations of the real interval operations and we show that the IEEE standard's specification of operations involving the signed infinities, signed zeros, and the exact/inexact flag are such as to make a correct and optimal implementation more efficient. From the resulting theorems, we derive data that are sufficiently detailed to convert directly to a program for efficiently implementing the interval operations. Finally, we extend these results to the case of general intervals, which are defined as connected sets of reals that are not necessarily closed.

In this paper we describe the syntax, semantics, and implementation of the constraint logic programming language CLP(F) and we prove that the implementation is sound. A CLP(F) constraint is a conjunction of equations and inequations in a first order theory of analytic univariate functions over the reals. The theory allows vector-valued functions over closed intervals to be constrained in several ways, including specifying functional equations (possibly involving the differentiation operator) that must hold at each point in the domain, arithmetic constraints on the value of a function at a particular point in its domain, and bounds on the range of a function over its domain. After describing the syntax and semantics of the constraint language for CLP(F) and giving several examples, we show how to convert these analytic constraints into a subclass of simpler functional constraints which involve neither differentiation nor evaluation of functions. We then present an algorithm for solving these latter constraints and prove that it is sound. This implies the soundness of the CLP(F) interpreter. We also provide some timing results from an implementation of CLP(F) based on GNU Prolog. The current implementation is able to solve a wide variety of analytic constraints, but on particular classes of constraints (such as initial value problems for autonomous ODEs), it is not competitive with other non-constraint based, interval solvers such as Lohner's AWA system. CLP(F) should be viewed as a first step toward the long term goal of developing a practical, declarative, logic-based approach to numerical analysis.

This paper consists of two parts: the first provides the theoretical foundations for analyzing parallel programs and illustrates how the theory can be applied to estimate the execution time of a class of parallel programs being executed on a MIMD computer. The second part describes a program analysis system, based on the theoretical model, which allows a user to interactively analyze the results of executing (or simulating the execution) of such parallel programs. Several examples illustrating the use of the tool are presented. A novel contribution is the separation (both at the conceptual and the implementation levels) of the machine-independent and the machine-dependent parts of the analysis. This separation enables the users of the system to establish speed-up curves for machines having varying characteristics.

article Toward the partial evaluation of CLP languages Share on Authors: Timothy J. Hickey Department of Computer Science, Brandeis University Department of Computer Science, Brandeis UniversityView Profile , Donald A. Smith Department of Computer Science, Brandeis University Department of Computer Science, Brandeis UniversityView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 9Sept. 1991 pp 43–51https://doi.org/10.1145/115866.115871Online:01 May 1991Publication History 12citation241DownloadsMetricsTotal Citations12Total Downloads241Last 12 Months3Last 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 SiteGet Access

CLP*(D) is a class of constraint logic programming languages which incorporates the notion of abstraction. Predicates in CLP*(D) are (potentially) infinite rational trees which represent abstractions of constraint expressions. This view of predicates as constraint abstractions was motivated by the language Scheme, where closures are viewed as abstractions of functional expressions. A semantics and an efficient implementation of the language are provided, along with several examples of the novel programming techniques provided by this class of languages.

The first part of the paper shows that previous theoretical work on the semantics of probabilistic programs (Kozen) and on the correctness of performance annotated programs (Ramshaw) can be used to automate the average-case analysis of simple programs containing assignments, conditionals, and loops. A performance compiler has been developed using this theoretical foundation. The compiler is described, and it is shown that special cases of symbolic simplifications of formulas play a major role in rendering the system usable. The performance compiler generates a system of recurrence equations derived from a given program whose efficiency one wishes to analyze. This generation is always possible, but the problem of solving the resulting equations may be complex. The second part of the paper presents an original method that generalizes the previous approach and is applicable to functional programs that make use of recursion and complex data structures. Several examples are presented, including an analysis of binary tree sort. A key feature of the analysis of such programs is that distributions on complex data structures are represented using attributed probabilistic grammars.

This paper presents the material needed for exposing the reader to the advantages of using Prolog as a language for describing succinctly most of the algorithms needed in prototyping and implementing compilers or producing tools that facilitate this task. The available published material on the subject describes one particular approach in implementing compilers using Prolog. It consists of coupling actions to recursive descent parsers to produce syntax-trees which are subsequently utilized in guiding the generation of assembly language code. Although this remains a worthwhile approach, there is a host of possibilities for Prolog usage in compiler construction. The primary aim of this paper is to demonstrate the use of Prolog in parsing and compiling. A second, but equally important, goal of this paper is to show that Prolog is a labor-saving tool in prototyping and implementing many non-numerical algorithms which arise in compiling, and whose description using Prolog is not available in the literature. The paper discusses the use of unification and nondeterminism in compiler writing as well as means to bypass these (costly) features when they are deemed unnecessary. Topics covered include bottom-up and top-down parsers, syntax-directed translation, grammar properties, parser generation, code generation, and optimizations. Newly proposed features that are useful in compiler construction are also discussed. A knowledge of Prolog is assumed.

Let S be the set of all strings of length n generated by a given context-free grammar. A uniform random generator is one which produces strings from S with equal probability. In generating these strings, care must be taken in choosing the disjuncts that form the right-hand side of a grammar rule so that the produced string will have the specified length. Uniform random generators have applications in studying the complexity of parsers, in estimating the average efficiency of theorem provers for the propositional calculus, in establishing a measure of ambiguity of a grammar, etc. Two methods are presented for generating uniform random strings in an unambiguous context-free language. The first method will generate a random string of length n in linear time, but must use a precomputed table of size $O(n^{r + 1} )$, where r is the number of nonterminals in the grammar used to specify the language. The second method precomputes part of the table and calculates the other entries as they are called for. It requires only linear space, but uses $O(n^2 (\log n)^2 )$ time to generate each string. Both methods generate strings by leftmost derivations where the probability that a given production will be used depends on the history of the derivation. It is also shown that, in the special cases of finite-state or linear languages, the generation can be performed in linear time with constant space.

article Free Access Share on Upper Bounds for Speedup in Parallel Parsing Authors: Jacques Cohen Computer Science Program, Brandeis University, Waltham, MA Computer Science Program, Brandeis University, Waltham, MAView Profile , Timothy Hickey Mathematics Department, University of Chicago, Chicago, IL Mathematics Department, University of Chicago, Chicago, ILView Profile , Joel Katcoff Kaye, Scholer, Fierman, Hays and Handler, 425 Park Avenue, New York, NY Kaye, Scholer, Fierman, Hays and Handler, 425 Park Avenue, New York, NYView Profile Authors Info & Claims Journal of the ACMVolume 29Issue 2April 1982 pp 408–428https://doi.org/10.1145/322307.322316Published:01 April 1982Publication History 26citation413DownloadsMetricsTotal Citations26Total Downloads413Last 12 Months17Last 6 weeks5 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Determining volumes of convex n-dimensional polyhedra defined by a linear system of inequalities is useful in program analysis Two methods for computing these volumes are proposed (1) summing the volumes of stmphces which form the polyhedron, and (2) summing the volumes of (increasingly smaller) paralleleplpeds which can be fit into the polyhedron Assuming that roundoff errors are small, the first method is analytically exact whereas the second one converges to the exact solution at the expense of addmonal computer time Examples of polyhedra whose volumes were computed by programs representing the algorithms are also provided