Papers and Publications

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.

• Computer Science Education
• Scheduling Algorithms
• Bioinformatics
• Assembly Planning
• Miscellaneous
• Software Packages

Computer Science Education

Data Structures & Algorithms in Python

Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser

Wiley, 2013, 768 pages

ISBN: 978-1-1182-9027-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 Transition Guide from Python 2.x to Java (coming soon)

A Graphics Package for the First Day and Beyond

Michael H. Goldwasser and David Letscher

Proceedings of the 40^th 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 13^th 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 13^th 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 22^nd 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 12^th 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 34^th 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 33^rd 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 15^th 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 12^th 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 15^th 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 11^th 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 40^th 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 34^th 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 33^rd 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).