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

Data Structures & Algorithms in Java, Sixth Edition
Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
Wiley, 2014, 736 pages
ISBN: 978-1-118-77133-4
Data Structures & Algorithms in Python
Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
Wiley, 2013, 768 pages
ISBN: 978-1-118-29027-9
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
Supplements:
A Transition Guide from Python 2.x to C++
    

A Graphics Package for the First Day and Beyond
Michael H. Goldwasser and David Letscher
Proceedings of the 40th Annual SIGCSE Technical Symposium on Computer Science Education (SIGCSE), Chattanooga, Tennessee, Mar. 4-7, 2009, pp. 206-210.
DOI:10.1145/1539024.1508945
Download as: [ abstract, pdf, pdf.gz, ps, ps.gz ]
A brief summary appeared earlier as
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, p. 325.
DOI:10.1145/1384271.1384369
Download as: [ abstract, pdf, pdf.gz, ps, ps.gz ]

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, pp. 42-46.
DOI:10.1145/1384271.1384285
Download as: [ abstract, pdf, pdf.gz, ps, ps.gz ]

Using Python to Teach Object-Oriented Programming
Michael H. Goldwasser and David Letscher
Presented at PyCon 2008.
Download as: [ 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
Download as: [ 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
Download as: [ 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
Download as: [ abstract, pdf, pdf.gz ]

A Gentle Introduction to Linked Lists
Michael H. Goldwasser
Poster at the 34th Annual SIGCSE Technical 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 Technical Symposium on Computer Science Education (SIGCSE), Covington, Kentucky, Feb. 27-Mar. 3, 2002, pp. 271-275.
DOI:10.1145/563340.563446
Download as: [ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Scheduling Algorithms

Dispatching Equal-Length Jobs to Parallel Machines to Maximize Throughput
David P. Bunde and Michael H. Goldwasser
Proceedings of the Twelfth Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Bergen, Norway, volume 6139 of Lecture Notes in Computer Science (Springer-Verlag, Berlin), Jun. 2010, pp. 346-358.
Download as: [ abstract, pdf ]

Online Nonpreemptive Scheduling of Equal-Length Jobs on Two Identical Machines
Michael H. Goldwasser and Mark Pedigo
ACM Transactions on Algorithms, 5(1), 2008
DOI:10.1145/1435375.1435377
Download as: [ 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.
DOI:10.1007/117852936_13
Download as: [ abstract, pdf, pdf.gz ]

A Simpler Competitive Analysis for Scheduling Equal-length Jobs on One Machine with Restarts
Michael H. Goldwasser and Arundhati Bagchi Misra
Information Processing Letters, 107(6):240-245, August 2008
DOI:10.1016/j.ipl.2008.03.003
Download preprint as: [ abstract, pdf, pdf.gz, ps, ps.gz ]

Admission Control with Immediate Notification
Michael H. Goldwasser and Boris Kerbikov
Journal of Scheduling, 6(3):269-285, 2003.
DOI:10.1023/A:1022956425198
Download as: [ 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.
DOI:10.1023/A:1022994010777
Download as: [ 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.
DOI:10.1145/314500.314592
Download as: [ 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, 34(6):1493-1515, 2005.
DOI:10.1137/S0097539704445202
Download as: [ 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.
DOI:10.1145/982792.982926
Download as: [ 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.
DOI:10.1089/cmb.2005.12.6380
Download preprint as: [ abstract, pdf, pdf.gz, ps, ps.gz ]
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.
DOI:10.1145/974614.974650
Download as: [ 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.
DOI:10.1016/j.jcss.2004.08.001
Download preprint as: [ abstract, pdf, pdf.gz, ps, ps.gz ]
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.
DOI:10.1145/645907.673125
Download as: [ 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.
Download as: [ 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.
Download as: [ 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.
Download as: [ 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.
Download as: [ 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.
Download as: [ abstract, pdf, pdf.gz, ps, ps.Z, ps.gz ]

Miscellaneous

A Survey of Buffer Management Policies for Packet Switches
Michael H. Goldwasser
SIGACT News 41(1):100-128, 2010.
DOI:10.1145/1753171.1753195
Download as: [ abstract, pdf, pdf.gz, ps, ps.gz ]

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.
Download as: [ 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.
Download as: [ 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.
DOI:10.1145/220279.220337
Download as: [ 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.
DOI:10.1145/202840.202847
Download as: [ 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 related article appears as
A Graphics Package for the First Day and Beyond
Michael H. Goldwasser and David Letscher
Proceedings of the 40th Annual SIGCSE Technical Symposium on Computer Science Education (SIGCSE), Chattanooga, Tennessee, Mar. 4-7, 2009, pp. 206-210.
DOI:10.1145/1539024.1508945
Download as: [ abstract, pdf, pdf.gz, ps, ps.gz ]

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 Technical 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 Technical 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 July 2014
My Home Page | Courses | Publications | Math/CS Dept | SLU