article

An alternative problem for backtracking and bounding

Authors:

Timothy J. Rolfe,

Paul W. PurdomAuthors Info & Claims

ACM SIGCSE Bulletin, Volume 36, Issue 4

Pages 83 - 84

https://doi.org/10.1145/1041624.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

Cited By

View all

González-Morris G(2006)Further thoughts on backtracking and boundingWorking group reports on ITiCSE on Innovation and technology in computer science education10.1145/1189215.1189167(46-47)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189215.1189167
González-Morris G(2006)Further thoughts on backtracking and boundingACM SIGCSE Bulletin10.1145/1189136.118916738:4(46-47)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189136.1189167

Recommendations

An alternative problem for backtracking and bounding
ITiCSE-WGR '04: Working group reports from ITiCSE on Innovation and technology in computer science education

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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGCSE Bulletin Volume 36, Issue 4

December 2004

145 pages

ISSN:0097-8418

DOI:10.1145/1041624

Issue’s Table of Contents

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

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

Published in SIGCSE Volume 36, Issue 4

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
333
Total Downloads

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

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

González-Morris G(2006)Further thoughts on backtracking and boundingWorking group reports on ITiCSE on Innovation and technology in computer science education10.1145/1189215.1189167(46-47)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189215.1189167
González-Morris G(2006)Further thoughts on backtracking and boundingACM SIGCSE Bulletin10.1145/1189136.118916738:4(46-47)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189136.1189167

View Options

Login options

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

Cited By

Recommendations

An alternative problem for backtracking and bounding

Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms

Characterizing negabent boolean functions over finite fields