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

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 34^th 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 33^rd 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 15^th 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 12^th 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 15^th 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 11^th 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 34^th 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 33^rd 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).