COMPUTER SCIENCE TECHNICAL REPORTS

1995 SERIES

SCHOOL OF COMPUTER SCIENCE

CARNEGIE MELLON UNIVERSITY

PITTSBURGH, PA  15213-3891

NOTE: Please read this Copyright notice before proceeding.

CMU-CS-95-100

Efficient Parallel Algorithms for Planar DAGs
Stephen Guattery, Gary L. Miller
May 1995
66 pages

CMU-CS-95-101

PADO: Learning Tree Structured Algorithms for Orchestration into an Object Recognition System
Astro [Eric] Teller, Manuela Veloso
February 1995
33 pages

CMU-CS-95-102 (Unavailable via ftp)

Competitive Analysis of Call Admission Algorithms that Allow Delay
Anja Feldmann, Bruce Maggs, Jiri Sgall, Daniel D. Sleator, Andrew Tomkins
January 1995
35 pages

CMU-CS-95-103

Stable Function Approximation in Dynamic Programming
Geoffrey J. Gordon
January 1995
23 pages

CMU-CS-95-104 (Technical Report)

CMU-CS-95-104 (Errata Sheet)

Modeling Foreshortening in Stereo Vision using Local Spatial Frequency
Mark W. Maimone, Steven S. Shafer
January 1995
35 pages

CMU-CS-95-105

Using Ordered Binary-Decision Diagrams for Compressing Images and Image Sequences
Mike Starkey, Randy Bryant
January 1995
12 pages

CMU-CS-95-106

Unavailable to date

CMU-CS-95-107

The Scotch Parallel Storage Systems
Garth A. Gibson, Daniel Stodolsky, Fay W. Chang, William V. Courtright II, Chris G. Demetriou, Eka Ginting, Mark Holland, Qingming Ma, LeAnn Neal, R. Hugo Patterson, Jiawen Su, Rachad Youssef, Jim Zelenka
January 1995
11 pages

CMU-CS-95-108 CMU-CS-95-108A.ps

Problem Decomposition for Reuse
Daniel Jackson, Michael Jackson
January 1995
37 pages

CMU-CS-95-110

Abstract Models of Memory Management
Greg Morrisett, Matthias Felleisen, Robert Harper
January 1995
[Also appears as CMU-CS-FOX-95-01]
37 pages

CMU-CS-95-111

Formalizing Style to Understand Descriptions of Software Architecture
Gregory Abowd, Robert Allen, David Garlan
January 1995
32 pages

CMU-CS-95-112

Management of Speedup Mechanisms in Learning Architectures
John Cheng
Ph.D. Thesis
January 1995
169 pages

CMU-CS-95-113

Production Matching for Large Learning Systems
Robert B. Doorenbos
Ph.D. Thesis
January 1995
200 pages

CMU-CS-95-114

Implementing Distributed Server Groups for the World Wide Web
Michael Garland, Sebastian Grassia, Robert Monroe, Siddhartha Puri
January 1995
12 pages

CMU-CS-95-115

Cryptanalysis Techniques: An Example Using Kerberos
Jennifer Kay
September 1995
15 pages

CMU-CS-95-116

Task-Oriented Generation of Visual Sensing Strategies in Assembly Tasks
Jun Miura, Katsushi Ikeuchi
February 1995
43 pages

CMU-CS-95-117

CMU-CS-95-117A

Experiences Using DCE and CORBA to Build Tool for Creating Highly-Available Distributed Systems
Elmootazbellah N. Elnozahy, Vivek Ratan, Mark E. Segal
February 1995
15 pages

CMU-CS-95-118 [PLEASE REFERENCE CMU-CS-95-118R.ps -- Revised Version]

Teaching Mathematics to Software Engineers
Jeannette M. Wing
February 1995
23 pages

CMU-CS-95-118R

Hints to Specifiers
Jeannette M. Wing
May 1995
22 pages

CMU-CS-95-119

A Programming Interface for Application-Aware Adaptation in Mobile Computing
Brian D. Noble, Morgan Price, Mahadev Satyanarayanan
February 1995
14 pages

CMU-CS-95-120

Systematic Approach to the Design of Representation-Changing Algorithms
Eugene Fink
February 1995
36 pages

CMU-CS-95-121

The Occurrence of Continuation Parameters in CPS Terms
Olivier Danvy, Frank Pfenning
February 1995
23 pages

CMU-CS-95-122

Real-Time Specialization Track: Masters of Software Engineering (MSE) Program
Carol L. Hoover
March 1995
12 pages

CMU-CS-95-123

Human-Computer Interaction (HCI) Specialization Track: Masters of Software Engineering (MSE) Program
Carol L. Hoover
March 1995
13 pages

CMU-CS-95-124

Business Specialization Track: Masters of Software Engineering (MSE) Program
Carol L. Hoover
March 1995
29 pages

CMU-CS-95-125

A Robust Parsing Algorithm for Link Grammars
Dennis Grinberg, John Lafferty, Daniel Sleator
August 1995

CMU-CS-95-126

Improving Data Consistency in Mobile Computing Using Isolation-Only Transactions
Qi Lu, Mahadev Satyanarayanan
March 1995
8 pages

CMU-CS-95-127

Specification Matching of Software Components
Amy Moormann Zaremski, Jeannette M. Wing
March 1995
23 pages

CMU-CS-95-128

Model Checking Software Systems: A Case Study
Jeannette M. Wing, Mandana Vaziri-Farahani
March 1995
27 pages

CMU-CS-95-129 (Temporarily unavailable for ftp)

Knowledge Tracing: Modeling the Acquisition of Procedural Knowledge
Albert T. Corbett, John R. Anderson
March 1995
[Also appears as Human-Computer Interaction Institute Report CMU-HCII-95-101]
21 pages

CMU-CS-95-130 (Unavailable via ftp)

Extending End-User Programming in a Visual Shell with Programming by Demonstration and Graphical Language Techniques
Francesmary Modugno
Ph.D. Thesis
March 1995
334 pages

CMU-CS-95-130A (Unavailable via ftp)

APPENDIX A: User Study Materials Extending End-User Programming in a Visual Shell with Programming by Demonstration and Graphical Language Techniques
Francesmary Modugno
Ph.D. Thesis
March 1995

CMU-CS-95-131

Tight Analyses of Two Local Load Balancing Algorithms
Bhaskar Ghosh, F. Tom Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa, Robert E. Tarjan, David Zuckerman
August 1995
29 pages

CMU-CS-95-132

CMU-CS-95-132A

CMU-CS-95-132B

Are Case Studies a Good Teaching Tool for CS1?
Jacobo Carrasquel
January 1995
7 pages

CMU-CS-95-133

Everyday Believability
Garrett A. Pelton, Jill Fain Lehman
March 1995
14 pages

CMU-CS-95-134 [See CMU-CS-95-134R.ps]

Informed Prefetching and Caching
R. Hugo Patterson, Garth A. Gibson, Eka Ginting, Daniel Stodolsky, Jim Zelenka
May 1995
26 pages

CMU-CS-95-134R

Informed Prefetching and Caching
R. Hugo Patterson, Garth A. Gibson, Eka Ginting, Daniel Stodolsky, Jim Zelenka
August 1995
This is a revised version of CMU-CS-95-134, to appear in the Proceedings of the 15th Symposium on Operating Systems Principles (SOSP).
17 pages (conference format)

CMU-CS-95-135

An Integral Approach to Free-form Object Modeling
Hueng-Yeung Shum, Martial Hebert, Katsushi Ikeuchi, Raj Reddy
May 1995
34 pages

CMU-CS-95-136

Abstractions and Implementations for Architectural Connections
Mary Shaw, Robert DeLine, Gregory Zelesnik
March 1995

CMU-CS-95-137

Dome: Parallel Programming in a Heterogeneous Multi-User Environment
Jose Nagib Cotrim Arabe, Adam Beguelin, Bruce Lowekamp, Erik Seligman, Mike Starkey, Peter Stephan
April 1995
28 pages

CMU-CS-95-138

Visual Analysis of High DOF Articulated Objects with Application to Hand Tracking
James M. Rehg
Ph.D. Thesis (Electrical and Computer Engineering)
April 1995
140 pages

CMU-CS-95-139

Behavior-based Language Generation for Believable Agents
A. Bryan Loyall, Joseph Bates
March 1995
19 pages

CMU-CS-95-140

Bit-Level Analysis of an SRT Divider Circuit
Randal E. Bryant
April 1995
11 pages

CMU-CS-95-141

Removing the Genetics from the Standard Genetic Algorithm
Shumeet Baluja, Rich Caruana
May 1995
11 pages

CMU-CS-95-142 CMU-CS-95-142A.ps, CMU-CS-95-142B.ps

Speech Recognition Using Neural Networks
Joseph Tebelskis
Ph.D. Thesis
May 1995

CMU-CS-95-143

Using the Representation in a Neural Network's Hidden Layer for
Task-Specific Focus of Attention
Shumeet Baluja, Dean Pomerleau
May 1995
10 pages

CMU-CS-95-144

Inducing Features of Random Fields
Stephen Della Pietra, Vincent Della Pietra, John Lafferty
May 1995
38 pages

CMU-CS-95-145

A Model Analysis of Staged Computation
Rowan Davies, Frank Pfenning
May 1995
[Also appears as CMU-CS-FOX-95-02]
25 pages

CMU-CS-95-146

Reflectance Analysis for 3D Computer Graphics Model Generation
Yoichi Sato, Katsushi Ikeuchi
June 1995

CMU-CS-95-147

Unavailable to Date

CMU-CS-95-148 CMU-CS-95-148A.ps

Lightweight Languages for Interactive Graphics
Scott Draves
May 1995
52 pages

CMU-CS-95-149

Evaluating Job Scheduling Techniques for Highly Parallel Computers
Takashi Suzuoka, Jaspal Subhlok, Thomas
August 1995
11 pages

CMU-CS-95-150

Higher-Order Superposition for Dependent Types
Roberto Virga
May 1995
34 pages

CMU-CS-95-151 (Unavailable via ftp)

Proceedings of the First International Workshop on Architectures for Software Systems
David Garlan, Editor
April 1995
301 pages

CMU-CS-95-152

Application of Convex Sampling to Optimization and Contingency Table Generation/Counting
John Mount
Ph.D. Thesis
May 1995
116 pages

CMU-CS-95-153

Virtualiized Reality: Concept and Early Results
Takeo Kanade, P.J. Narayanan, Peter Rander
August 1995
17 pages

CMU-CS-95-154

Strong Restricted-Orientation Convexity
Eugene Fink, Derick Wood
June 1995
27 pages

CMU-CS-95-155

Compiler Directed Architecture-Dependent Communication Optimizatons
Susan Karen Hinrichs
Ph.D. Thesis
June 1995
152 pages

CMU-CS-95-156

Model Checking Cache Coherence Protocols for Distributed File Systems
Mandana Vaziri-Farahani
May 1995
32 pages

CMU-CS-95-157

An Efficient Technique for Tracking Nondeterministic Execution and its Applications
Elmootazbellah N. Elnozahy
May 1995
21 pages

CMU-CS-95-158 (See revised version CMU-CS-95-158R)

Human Face Detection in Visual Scenes
Henry A. Rowley, Shumeet Baluja, Takeo Kanade
July 1995
19 pages

CMU-CS-95-158R

Human Face Detection in Visual Scenes
Henry A. Rowley, Shumeet Baluja, Takeo Kanade
November 1995
19 pages

CMU-CS-95-159

Hybrid Decision Diagrams: Overcoming the Limitations of MTBDDs and BMDs
Edmund Clarke, Masahiro Fujita, Xudong Zhao
April 1995
21 pages

CMU-CS-95-160

Applications of Multi-Terminal Binary Decision Diagrams
Edmund Clarke, Masahiro Fujita, Xudong Zhao
April 1995
21 pages

CMU-CS-95-161

Word Level Symbolic Model Checking: A New Approach for Verifying Arithmetic Circuits
Edmund Clarke, Xudong Zhao
May 1995
23 pages

CMU-CS-95-162

Design, Implementation, and Performance of a Scalable Multi-Camera Interactive Video Capture System
Martin Frankel, Jon A. Webb
June 1995
17 pages

CMU-CS-95-163

A Study of Higher-order Sequential Computation
Shai Geva
Ph.D. Thesis
August 1995
96 pages

CMU-CS-95-164

Natural Negotiation for Believable Agents
W. Scott Reilly, Joseph Bates
June 1995
25 pages

CMU-CS-95-165 (Unavailable via ftp)

Collected Papers of the Soar/IFOR Project: Spring 1995
W. Lewis Johnson, Randolph M. Jones, Frank V. Koss, John E. Laird, Jill F. Lehman, Paul E. Neilsen, Paul S. Rosenbloom, Robert Rubinoff, Karl B. Schwamb, Milind Tambe, Julie Van Dyke, Michael van Lent, and Robert E. Wray III
June 1995
[Published concurrently at the University of Michigan (CSE\-TR-242-95) and the University of Southern California Information Sciences Institute (ISI/SR-95-406)]
78 pages

CMU-CS-95-166 [See CMU-CS-95-166-R1.ps]

The Amulet Reference Manuals
Brad A. Myers, Rich McDaniel, Alan Ferrency, Andy Mickish, Alex Klimovitski, Amy McGovern
[Also appears as CMU-HCII-95-102]
June 1995
236 pages

CMU-CS-95-166-R1

The Amulet V2.0 Reference Manual
Brad A. Myers, Alan Ferrency, Rich McDaniel, Robert C. Miller, Patrick Doane, Andy Mickish, Alex Klimovitski
[Also appears as CMU-HCII-95-102-R1, Revised Version of CMU-CS-95.166.ps]
February 1996

CMU-CS-95-167

On the Relevance of Communication Costs of Rollback-Recovery Protocols
Elmootazbellah N. Elnozahy
June 1995
16 pages

CMU-CS-95-168

Automatic Generation of Parallel Programs with Dynamic Load Balancing for a Network of Workstations
Bruce S. Siegell
Ph.D. Thesis (Electrical and Computer Engineering)
May 1995
215 pages

CMU-CS-95-169

NESL User's Manual [For NESL Version 3.1]
Guy E. Blelloch, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha
September 1995
31 pages

CMU-CS-95-170

NESL: A Nested Data-Parallel Language[Version 3.1]
Guy E. Blelloch
September 1995
66 pages

CMU-CS-95-171

Typed Closure Conversion
Yosuhiko Minamide, Greg Morrisett, Robert Harper
[Also appears as CMU-CS-FOX-95-05]
July 1995
39 pages

CMU-CS-95-172

A Preliminary Model of Expert Programming
Erik M. Altmann, Bonnie E. John
July 1995
[Also appears as CMU-HCII-95-103]
17 pages

CMU-CS-95-173 (Unavilable via ftp)

The Paraperspective and Projective Factorization Methods for Recovering Shape and Motion
Conrad J. Poelman
Ph.D. Thesis
July 1995
146 pages

CMU-CS-95-174

Using Dynamic Sets to Speed Search in World Wide Information Systems
David C. Steere
March 1995
18 pages

CMU-CS-95-175 (Unavailable via Date)

Learning Search Control Knowledge to Improve Plan Quality
Maria Alicia Perez
Ph.D. Thesis
July 1995
275 pages

CMU-CS-95-176

Amulet's Dynamic and Flexible Prototype-Instance Object and Constraint System in C++
Rich McDaniel, Brad A. Myers
July 1995
[Also appears as CMU-HCII-95-104]
22 pages

CMU-CS-95-177

The Effect of Representation and Knowledge on Goal-Directed Exploration with Reinforcement-Learning Algorithms: The Proofs
Sven Koenig, Reid G. Simmons
October 1995
10 pages

CMU-CS-95-178

Exceptions Are Strictly More Powerful Than Call/CC
Mark Lillibridge
July 1995
11 pages

CMU-CS-95-179

Trace-based Program Analysis
Christopher Colby, Peter Lee
[Also appears as CMU-CS-FOX-95-04]
July 1995
27 pages

CMU-CS-95-180

Sequence Types for Functional Languages
Edoardo S. Biagioni
[Also appears as CMU-CS-FOX-95-06]
August 1995
23 pages

CMU-CS-95-181

CMU-CS-95-181A (special titlepage)

Fast Polygonal Approximation of Terrains and Height Fields
Michael Garland, Paul S. Heckbert
September 1995
41 pages

CMU-CS-95-182 CMU-CS-95-182A.ps (Special CS Title Page)

Fourier Formulation of Illumination Optics and Computer Automated Reflector Design
Robert D. Stock
Ph D. Thesis (Physics Department)
August 1995
166 pages

CMU-CS-95-183

The Harmonic Sieve: A Novel Application of Fourier Analysis to Machine Learning Theory and Practice
Jeffrey C. Jackson
Ph.D. Thesis
August 1995
154 pages

CMU-CS-95-184

Exploiting Structured Data in Wide-Area Information Systems
John Ockerbloom
August 1995
15 pages

CMU-CS-95-185

Exploiting Weak Connectivity for Mobile File Access
Lily B. Mummert, Maria R. Ebling, Mahadev Satyanarayanan
August 1995
15 pages

CMU-CS-95-186

Video Skimming for Quick Browsing based on Audio and Image Characterization
Michael A. Smith, Takeo Kanade
July 1995
24 pages

CMU-CS-95-187 (Unavailable via ftp)

Applications of Graph-Theoretical Properties in Algorithms
Stephen Guattery
Ph.D. Thesis
September 1995
117 pages

CMU-CS-95-188

Smart Cards in Hostile Environments
Howard Gobioff, Sean Smith, J. Doug Tygar
September 1995
7 pages

CMU-CS-95-189

Evaluating a Multimedia Authoring Tool with Cognitive Walkthrough and Think-Aloud User Studies
Bonnie E. John, Matthew M. Mashyna
August 1995
[Also appears as CMU-HCII-95-105]
50 pages

CMU-CS-95-190 (Unavailable via ftp)

Color Image Quantization Enhancement Techniques
Jefferey A. Shufelt
September 1995
37 pages

CMU-CS-95-191

ECO: Efficient Collective Operations for Communications on Heterogeneous Networks
Bruce B. Lowekamp, Adam Beguelin
August 1995
24 pages

CMU-CS-95-192

Gigbit Nectar: Architecture and Performance
Peter Steenkiste
September 1995
23 pages

CMU-CS-95-193

An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics
Shumeet Baluja
September 1995
22 pages

CMU-CS-95-194 (Unpublished)

CMU-CS-95-195 (Unavailable via ftp)

Design and Evaluation of a Semi-Automated Site Modeling System
Yuan Hsieh
November 1995
80 pages

CMU-CS-95-196

Unavailable to date

CMU-CS-95-197

Spherical Representations: from EGI to SAI
Katsushi Ikeuchi, Martial Hebert
October 1995
29 pages

CMU-CS-95-198 (Unavailable via ftp)

SAR Target Recognition Based on Invariant Histograms and Deformable Template Matching
Katsushi Ikeuchi, Takeshi Shakunaga, Mark D. Wheeler, Taku Yamazaki
March 1996
40 pages

CMU-CS-95-199

Just Draw It! Programming by Sketching Storyboards
James A. Landay, Brad A. Myers
November 1995
[Also appears as CMU-HCII-95-106]
17 pages

CMU-CS-95-200

RAIDframe: Rapid Prototyping for Disk Arrays
Garth Gibson, William V. Courtright II, Mark Holland, Jim Zelenka
October 1995
19 pages

CMU-CS-95-201 (Unavailable via ftp)

On-line Call Admission for High-Speed Networks
Anja Feldmann
Ph.D. Thesis
October 1995
186 pages

CMU-CS-95-202

Detecting Shared Representations Using Type Inference
Robert O'Callahan, Daniel Jackson
September 1995
23 pages

CMU-CS-95-203

Unavailable to date

CMU-CS-95-204

Unavailable to date

CMU-CS-95-205

Optimizing ML with Run-Time Code Generation
Mark Leone, Peter Lee
December 1995
21 pages

CMU-CS-95-206 (Unavailable via ftp)

Proceedings of the Workshop on Value Function Approximation
Justin A. Boyan, Andrew W. Moore, Richard S. Sutton, Editors
July 1995
92 pages

CMU-CS-95-207

Broad Learning from Narrow Training: A Case Study in Robotics Soccer
Peter Stone, Manuela Veloso
November 1995
16 pages

CMU-CS-95-208

Lifelong Learning: A Case Study
Sebastian Thrun
November 1995
40 pages

CMU-CS-95-209

Clustering Learning Tasks and the Selective Cross-Task Transfer of Knowledge
Sebastian Thrun, Joseph O'Sullivan
November 1995
36 pages

CMU-CS-95-210

Tracking Human Faces in Real-Time
Jie Yang, Alex Waibel
November 1995
37 pages

CMU-CS-95-211 (Unpublished)

CMU-CS-95-212

On 3D Shape Similarity
Heung-yeung Shum, Martial Hebert, Katsushi Ikeuchi
November 1995
32 pages

CMU-CS-95-213

On 3D Shape Synthesis
Heung-yeung Shum, Martial Hebert, Katsushi Ikeuchi
November 1995
31 pages

CMU-CS-95-214

The Design and Evolution of a Distributed Measurement Framework
Brian D. Noble
December 1995
13 pages

CMU-CS-95-215

Iterative Estimation of Rotation and Translation using the Quaternion
Mark D. Wheeler, Katsushi Ikeuchi
December 1995
17 pages

CMU-CS-95-216

Unavailable to date

CMU-CS-95-217A CMU-CS-95-217B.ps, CMU-CS-95-217C.ps

Serious Putty: Topological Design for Variational Curves and Surfaces
William Welch
Ph.D. Thesis
December 1995
134 pages

CMU-CS-95-218

A Computational Meta Logic for the Horn Fragment of LF
Carsten Schurmann
Master's Thesis (Philosophy)
December 1995
159 pages

CMU-CS-95-219

Unavailable to date

CMU-CS-95-220

Unavailable to date

CMU-CS-95-221

Fast Planning Through Planning Graph Analysis
Avrim L. Blum, Merrick L. Furst
December 1995
22 pages

CMU-CS-95-222

Beating a Defender in Robotic Soccer: Memory-Based Learning of a Continuous Function
Peter Stone, Manuela Veloso
December 1995
11 pages

CMU-CS-95-223

Language Support for Mobile Agents
Frederick Colville Knabe
Ph.D. Thesis
December 1995
158 pages

CMU-CS-95-224 CMU-CS-95-224.append.ps (Appendix)

Formalizing the Uni-Processor Simplex Architecture
Jose German Rivera, Alejandro Andres Danylyszyn
December 1995
52 pages

CMU-CS-95-225

Safe and Efficient Persistent Heaps
Scott M. Nettles
Ph.D. Thesis
December 1995
208 pages

CMU-CS-95-226

Compiling with Types
Greg Morrisett
Ph.D. Thesis
December 1995
233 pages