JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Gries, David"
Now showing items 2140 of 59

Developing Two of Arsac's Funny Algorithms
Gries, David (Cornell University, 198511)In Some Funny Program (Ecole Normale Superieure, Paris, June 1985) J. Arsac discusses several algorithms, but not from the standpoint of their development. Here, we develop the algorithms given their specification using ... 
Educating the Programmer: Notation, Proofs, and the Development of Programs
Gries, David (Cornell University, 198004)The current state of affairs in programming is discussed. The opinion is expressed that effective programming requires more "mathematical maturity" than most programmers have. Further, education in formal logicc, which ... 
Engineering: Cornell Quarterly, Vol.20, No.2 (Autumn 1985): Twenty Years of Computer Science at Cornell
Gries, David; Teitelbaum, Tim; Reps, Thomas; Schneider, Fred B.; Babaoglu, Ozalp; Birman, Kenneth P.; Toueg, Sam; Krafft, Dean B.; Solworth, Jon A.; Duke, Diane; Fish, Michele (InternetFirst University Press, 1985)IN THIS ISSUE: Twenty Years of Computer Science at Cornell /2 David Gries ... Immediate Computation or How to Keep a Personal Computer Busy /12 Tim Teitelbaum and Thomas Reps ... Reaching Agreement: A Fundamental Task Even ... 
Equational Propositional Logic
Gries, David; Schneider, Fred B. (Cornell University, 199409)We formalize equational propositional logic, prove that it is sound and complete, and compare the equationalproof style with the more traditional Hilbert style. 
FaultTolerant Broadcasts
Schneider, Fred B.; Gries, David; Schlichting, Richard D. (Cornell University, 198309)A distributed program is presented that ensures delivery of a message to the functioning processors in a computer network, despite the fact that processors may fail at any time. All processor failures are assumedd to be ... 
Finding Repeated Elements
Misra, Jayadev; Gries, David (Cornell University, 198207)Two algorithms are presented for finding the values that occur more than $n \div k$ times in array b[O:n1]. The second algorithm requires time $O(n \log(k))$ and extra space $O(k)$. We prove that $O(n \log(k))$ is a ... 
Formal Justification of Underspecification for S5
Aaron, Eric; Gries, David (Cornell University, 199702)We formalize the notion of underspecification as a means of avoiding problems with partial functions in modal logic S5 and some semantically related logics. For these logics, underspecification respects validity, so ... 
Formal versus semiformal proof in teaching predicate logic
Gries, David (Cornell University, 199608)This space is left deliberately nonblank 
Formalizations Of Substitution Of Equals For Equals
Gries, David; Schneider, Fred B. (Cornell University, 199805)Inference rule "substitution of equals for equals" has been formalized in terms of simple substitution (which performs a replacement even though a free occurrence of a variable is captured), contextual substitution (which ... 
General Correctness: A Unification of Partial and Total Correctness
Jacobs, Dean; Gries, David (Cornell University, 198410)General correctness, which subsumes partial and total correctness, is defined for both weakest preconditions and strongest postconditions. Healthiness properties for generalcorrectness predicate transformers are more ... 
Generating a Random Cyclic Permutation
Gries, David; Xue, Jinyun (Cornell University, 198609)ABSTRACT NOT SUPPLIED 
The HopcroftTarjan Planarity Algorithm, Presentation and Improvements
Gries, David; Xue, Jinyun (Cornell University, 198804)We give a rigorous, yet, we hope, readable, presentation of the HopcroftTarjan linear algorithm for testing the planarity of a graph, using more modern principles and techniques for developing and presenting algorithms ... 
Insitu Inversion of a Cyclic Permutation
Feijen, W. H. J.; Van Gasteren, A. J. M.; Gries, David (Cornell University, 198509)An algorithm is developed for the insitu inversion of a cyclic permutation represented in an array. The emphasis is on the quo modo rather than the quod; we are interested in finding concepts and notations for dealing ... 
Inorder Traversal of a Binary Tree and its Inversion
Gries, David; Van de Snepscheut, Jan L.A. (Cornell University, 198711)ABSTRACT NOT AVAILABLE 
An Introduction to Proofs of Program Correctness for Teachers of CollegeLevel Introductory Programming Courses
Gries, David; Wadkins, Jeff (Cornell University, 199003)No abstract is available. 
Is Sometimes Ever Better Than Always?
Gries, David (Cornell University, 197806)The "intermittent assertion" method for proving programs correct is explained and compared to the conventional axiomatic method. Simple axiomatic proofs of iterative algorithms that compute recursively defined functions, ... 
A Linear Sieve Algorithm for Finding Prime Numbers
Gries, David; Misra, Jayadev (Cornell University, 197706)NO ABSTRACT SUPPLIED 
McLaren's Masterpiece
Gries, David; Prins, Jan F. (Cornell University, 198601)Abstract not available 
A Model and Temporal proof system for Networks of Processes
Nguyen, Van Long; Demers, Alan J.; Gries, David; Owicki, Susan S. (Cornell University, 198506)An approach is presented for modeling networks of processes that communicate exclusively through message passing. A process (or a network) is defined by its set of possible behaviors, where each behavior is an abstraction ... 
A Model and Temporal Proof System for Networks of Processes
Nguyen, Van Long; Gries, David; Owicki, Susan S. (Cornell University, 198411)A model and a sound and complete proof system for networks of processes in which component processes communicate exclusively through messages is given. The model, an extension of the trace model, can desribe both synchronous ...