My Home Page | Courses | Publications | Math/CS Dept | SLU

Papers and Publications

Michael H. Goldwasser


The copyright for most of these papers belongs to the respective publishers. I include the ACM copywrite statement below; others' are similar.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

Categories:

Computer Science Education

Object-Oriented Programming in Python
Michael H. Goldwasser and David Letscher
Prentice Hall, 2008, 700 pages
ISBN-10: 0-13-615031-4
ISBN-13: 978-0-13-615031-2

Teaching an Object-Oriented CS1 — with Python
Michael H. Goldwasser and David Letscher
Proceedings of the 13th Annual Conference on Innovation and Technology in Computer Science (ITiCSE), Madrid, Spain Jun. 30-Jul. 2, 2008, to appear.
[ abstract, pdf, pdf.gz, ps, ps.gz ]

A Python Graphics Package for the First Day and Beyond
Michael H. Goldwasser and David Letscher
Demonstration at the 13th Annual Conference on Innovation and Technology in Computer Science (ITiCSE), Madrid, Spain Jun. 30-Jul. 2, 2008, to appear.
[ abstract, pdf, pdf.gz, ps, ps.gz ]

Using Python to Teach Object-Oriented Programming
Michael H. Goldwasser and David Letscher
Presented at PyCon 2008.
[ abstract, pdf, pdf.gz, ps, ps.gz ]

Teaching Strategies for Reinforcing Structural Recursion with Lists
Michael H. Goldwasser and David Letscher
Companion to the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA Educators' Symposium), Montreal, Quebec, Canada, Oct. 2007, pp. 889-896
DOI:10.1145/1297846.1297940
[ abstract, pdf, pdf.gz, ps, ps.gz ]

Introducing Network Programming into a CS1 Course
Michael H. Goldwasser and David Letscher
Proceedings of the 12th Annual Conference on Innovation and Technology in Computer Science (ITiCSE), Dundee, Scotland, UK Jun. 25-27, 2007, pp. 19-22
DOI:10.1145/1269900.1268793
[ abstract, pdf, pdf.gz, ps, ps.gz ]

Providing Students Universal Access to a Centralized, Graphical Computing Environment
Michael H. Goldwasser and David Letscher
Proceedings of the Tenth Annual Conference on Innovation and Technology in Computer Science (ITiCSE), Monte da Caparica, Portugal Jun. 27-29, 2005, pp. 79-83.
DOI:10.1145/1067445.1067470
[ abstract, pdf, pdf.gz ]

A Gentle Introduction to Linked Lists
Michael H. Goldwasser
Poster at the 34th Annual SIGCSE Techinical Symposium on Computer Science Education (SIGCSE), Reno, Nevada, Feb. 2003.
A brief paper [doc]
Demo of Software [website]

A Gimmick to Integrate Software Testing Throughout the Curriculum
Michael H. Goldwasser
Proceedings of the 33rd Annual SIGCSE Techinical Symposium on Computer Science Education (SIGCSE), Covington, Kentucky, Feb. 27-Mar. 3, 2002, pp. 271-275.
DOI:10.1145/563340.563446
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Scheduling Algorithms

A Simpler Competitive Analysis for Scheduling Equal-length Jobs on One Machine with Restarts
Michael H. Goldwasser and Arundhati Bagchi Misra
To appear in Information Processing Letters
DOI:10.1016/j.ipl.2008.03.003
[ abstract, pdf, pdf.gz, ps, ps.gz ]

Online Non-preemptive Scheduling of Equal-length Jobs on Two Identical Machines
Michael H. Goldwasser and Mark Pedigo
To appear in ACM Transactions on Algorithms
[ abstract, pdf, pdf.gz, ps, ps.gz ]
Preliminary verison appeared in,
Proceedings of the Tenth Scandinavian Workshop on Algorithm Theory (SWAT), Riga, Latvia, volume 4059 of Lecture Notes in Computer Science (Springer-Verlag, Berlin), Jul. 2006, pp. 113-123.

Admission Control with Immediate Notification
Michael H. Goldwasser and Boris Kerbikov
Journal of Scheduling, 6(3):269-285, 2003.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control
Michael H. Goldwasser
Journal of Scheduling, 6(2):183-211, 2003.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]
Preliminary version appeared in:
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, Maryland, Jan. 1999, pp. 396-405.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Bioinformatics

Complexities for Generalized Models of Self-assembly
Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanes, and Robert T. Schweller
SIAM Journal of Computing, 24(6):1493-1515, 2005.
[ abstract, pdf, pdf.gz ]
Preliminary version appeared as:
Complexities for Generalized Models of Self-Assembly
Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, and Robert T. Schweller
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana, Jan. 2004, pp. 880-889.
[ abstract, pdf, pdf.gz, pdf.Z ]

Identifying Conserved Gene Clusters in the Presence of Homology Families
Xin He and Michael H. Goldwasser,
Journal of Computational Biology, 12(6):638--656, 2005.
Preliminary verison appeared as,
Identifying Conserved Gene Clusters in the Presence of Orthologous Groups
Xin He and Michael H. Goldwasser
Proceedings of the Eighth Annual International Conferences on Research in Computational Molecular Biology (RECOMB), San Diego, California, Mar. 2004, pp. 272-280.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications
Michael H. Goldwasser, Ming-Yang Kao, and Hsueh-I Lu
Journal of Computer and System Sciences, 70(2):128-144, 2005.
Preliminary verison appeared as,
Fast Algorithms for Finding Maximum-Density Segments of a Sequence with Applications to Bioinformatics
Michael H. Goldwasser, Ming-Yang Kao, and Hsueh-I Lu
Proceedings of the Second Annual Workshop on Algorithms in Bioinformatics (WABI), volume 2452 of Lecture Notes in Computer Science (Springer-Verlag, Berlin), 2002, pp. 157-171.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Assembly Planning

Complexity Measures for Assembly Sequences
Michael H. Goldwasser and Rajeev Motwani
International Journal of Computational Geometry and Applications, 9(4 & 5):371-417, 1999.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]
PhD Thesis appeared as,
Complexity Measures for Assembly Sequences
Michael Goldwasser
Technical Report No. STAN-CS-TR-97-1950, Department of Computer Science, Stanford University, 1997.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]
Preliminary results appeared as,
Complexity Measures for Assembly Sequences
Michael Goldwasser, Jean-Claude Latombe, and Rajeev Motwani
Proceedings of the 12th IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, Minnesota, Apr. 1996, pp. 1581-1587.
abstract, pdf, pdf.gz, ps, ps.Z, ps.gz

Intractability of Assembly Sequencing: Unit Disks in the Plane
Michael Goldwasser and Rajeev Motwani
Proceedings of the Fifth Annual Workshop on Algorithms and Data Structures (WADS), volume 1272 of Lecture Notes in Computer Science (Springer-Verlag, Berlin), 1997, pp. 307-320.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

An Efficient System for Geometric Assembly Sequence Generation and Evaluation
Bruce Romney, Cyprien Godard, Michael Goldwasser, and G. Ramkumar
Proceedings of the 15th ASME International Computers in Engineering Conference (CIE), Boston, Massachusetts, Sept. 1995, pp. 699-712.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Miscellaneous

Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges
edited by Michael H. Goldwasser, David S. Johnson, and Catherine C. McGeoch.
Volume 59 in the DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, RI, 2002.
ISBN 0-8218-2892-4

On External Memory Graph Traversal
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, and Jeffery R. Westbrook.
Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California, Jan. 2000, pp. 859-860.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Web Search Using Automated Classification
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, and Eli Upfal.
Sixth International World Wide Web Conference (WWW), Santa Clara, California, Apr. 1997, Poster POS725.
[ abstract, HTML, bw.pdf, bw.pdf.gz, bw.ps, bw.ps.Z, bw.ps.gz, color.pdf, color.pdf.gz, color.ps, color.ps.Z, color.ps.gz ]

An Implementation for Maintaing Arrangements of Polygons
Michael Goldwasser.
Proceedings of the 11th Symposium on Computational Geometry (SoCG), Vancouver, British Columbia, June 1995, pp. C32-33.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz , Sourcecode ]

A Survey of Linear Programming in Randomized Subexponential Time
Michael Goldwasser.
SIGACT News 26:2, 1995, pp. 96-104.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Software Packages

cs1graphics
cs1graphics is an object-oriented Python graphics module specifically designed for pedagogical use.
[website]

A Gentle Introduction to Linked Lists
A Java Applet that allows students to create and modify singly-linked lists, as embedded directly in memory.
[website]

A related poster was presented at the 34th Annual SIGCSE Techinical Symposium on Computer Science Education (SIGCSE), Reno, Nevada, Feb. 2003. A brief paper describes this project [doc].

autograde
autograde is a Perl script which automates the execution of student programs on various test inputs provided by the instructor and other students. The script is designed for use on a Unix/Linux system.
[ website ]

A related article appears in Proceedings of the 33rd Annual SIGCSE Techinical Symposium on Computer Science Education (SIGCSE), Covington, Kentucky, Feb. 27-Mar. 3, 2002, pp. 271-275.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

arrange
arrange is a package written in C for maintaining arrangements of polygons in either the plane or on the sphere. Polygons may be degenerate, and hence represent arrangements of lines. A randomized incremental construction algorithm is used, and efficient point location on the arrangement is supported. Polygons may be inserted but not deleted from the arrangement.
[ Sourcecode ]

A related article appears in Proceedings of the 11th Symposium on Computational Geometry (SoCG), Vancouver, British Columbia, June 1995, pp. C32-33.
[ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]
The software is also included in:
Nina Amenta's Directory of Computational Geometry Software
Stony Brook Algorithm Repository (rating 9 of 10).

Michael H. Goldwasser
Last modified: Thursday, 10 April 2008
My Home Page | Courses | Publications | Math/CS Dept | SLU