Article

An alternative problem for backtracking and bounding

Authors:

Timothy J. Rolfe,

Paul W. PurdomAuthors Info & Claims

ITiCSE-WGR '04: Working group reports from ITiCSE on Innovation and technology in computer science education

Pages 83 - 84

https://doi.org/10.1145/1044550.1041664

Published: 28 June 2004 Publication History

Get Access

Abstract

One of the programming problems in the 2002 Pacific Northwest regional ACM ICPC contest provides a new way to teach backtracking and also provides a very powerful example of a forward-looking bounding function. This article presents the problem, the bounding function, and timing information of implementations with and without the bounding function. It also provides the URL for access to the programs themselves.

References

[1]

Dean S. Clark, "A Combinatorial Theorem on Circulant Matrices", Amer. Math. Monthly, Vol. 92, No. 10 (December 1985), pp. 725 ff. For those whose institutions are participants in JSTOR (Journal STORage), http://www.jstor.org/browse/#Mathematics provides access to this article --- select American Mathematical Monthly, navigate to Vol. 92, No. 10, and search for "Clark". He later coauthored a paper on n-entry circular permutations. Dean S. Clark and Stanford S. Bonan, "Experimental Gambling System", Mathematics Magazine, Vol. 60, No. 4 (October 1987), pp. 217 ff. Again, http://www.jstor.org/browse/#Mathematics provides access --- select Mathematics Magazine, navigate to Vol. 60, No. 4, then search for "Clark".

Google Scholar

[2]

Martin Gardner, "987654321", Isaac Asimov's Science Fiction Magazine, August 1986, p. 100.

Google Scholar

[3]

Timothy J. Rolfe, "Recurse Around the Clock", Mathematics and Computer Education, Vol. 21, No. 2 (Spring, 1987), pp. 98--104.

Digital Library

Google Scholar

[4]

See Problem E in http://www.acmcontest-pacnw.org/ProblemSet/2002/forweb.zip

Google Scholar

[5]

See http://icpc.baylor.edu/icpc/

Google Scholar

[6]

Timothy Rolfe, "Backtracking Algorithms", Dr. Dobb's Journal, Vol. 29, No. 5 (May 2004), pp. 48, 50--51.

Google Scholar

[7]

These implementations (which were developed as the instructor's solution when the problem was given as an assignment in an Algorithms course) are available through the following URL: http://penguin.ewu.edu/~trolfe/BoundClock/Implementation.html

Google Scholar

Recommendations

An alternative problem for backtracking and bounding

One of the programming problems in the 2002 Pacific Northwest regional ACM ICPC contest provides a new way to teach backtracking and also provides a very powerful example of a forward-looking bounding function. This article presents the problem, the ...
Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms

We consider a class of multivariate recurrences frequently arising in the worst-case analysis of Davis-Putnam-style exponential-time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these ...
Characterizing negabent boolean functions over finite fields
SETA'12: Proceedings of the 7th international conference on Sequences and Their Applications

We consider negabent Boolean functions that have Trace representation. To the best of our knowledge, this is the first ever work on negabent functions with such representation. We completely characterize negabent quadratic monomial functions. We also ...

Comments

Information & Contributors

Information

Published In

ITiCSE-WGR '04: Working group reports from ITiCSE on Innovation and technology in computer science education

June 2004

152 pages

ISBN:9781450377942

DOI:10.1145/1044550

Publications Chair:
Henry M. Walker
Grinnell College, Grinnell, Iowa

ACM SIGCSE Bulletin Volume 36, Issue 4
December 2004
145 pages
ISSN:0097-8418
DOI:10.1145/1041624
Issue’s Table of Contents

Permission to make digital or hard copies of all or part 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, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ITiCSE04

Sponsor:

SIGCSE

ITiCSE04: Innovation and Technology in Computer Science Education

June 28 - 30, 2004

Leeds, United Kingdom

Acceptance Rates

Overall Acceptance Rate 552 of 1,613 submissions, 34%

Upcoming Conference

ITiCSE '25

Sponsor:
sigcse

Innovation and Technology in Computer Science Education

June 27 - July 2, 2025

Nijmegen , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
333
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Recommendations