Article

Teaching the power of randomization using a simple game

Authors:

Yana Kortsarts,

Jeffrey RufinusAuthors Info & Claims

SIGCSE '06: Proceedings of the 37th SIGCSE technical symposium on Computer science education

Pages 460 - 463

https://doi.org/10.1145/1121341.1121486

Published: 03 March 2006 Publication History

Get Access

Abstract

Any deterministic algorithm can be viewed as a game between the algorithm player and the input player. A randomized algorithm can be viewed as a mixed strategy for the first player, used to minimize the disadvantage of being the first to reveal its move. We suggest a simple and accessible guessing game that can serve as both a way to explain notions in algorithms (like worst case input) to students and also to illustrate the power of randomization, presented in an intuitive way.

References

[1]

S. Arora and C. Lund and R. Motwani and M. Sudan and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of ACM, 45(3):501--555, 1998.

Digital Library

Google Scholar

[2]

G. J. Brebner and L. G. Valiant, Universal schemes for parallel communication. Proceedings of the thirteenth annual ACM symposium on Theory of computing, Pages: 263--277, 1981.

Digital Library

Google Scholar

[3]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to algorithms. The MIT Press, 2nd edition, 2001.

Digital Library

Google Scholar

[4]

S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein and J. Wein. Improved scheduling algorithms for minsum criteria. ICALP '96, 875--886.

Digital Library

Google Scholar

[5]

A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive paging algorithms. Journal of Algorithms archive Volume 12(4): 685--699 1991.

Digital Library

Google Scholar

[6]

O. Goldreich, S. Micali, A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):690--728, 1991.

Digital Library

Google Scholar

[7]

L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. SODA'96, 142--151. 42--151, Jan 1996.

Digital Library

Google Scholar

[8]

L. A. Hall, A. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line nd on-line approximation algorithms. Math. Operations Research 22:513--544, 1997.

Digital Library

Google Scholar

[9]

G. Kalai, A subexponential randomized simplex algorithm, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, 475--482, 1992.

Digital Library

Google Scholar

[10]

R. M. Karp, E. Upfal and A. Wigderson. Constructing a perfect matching is in random NC. Combinatorica Volume 6(1):35--48, 1986.

Digital Library

Google Scholar

[11]

M. Queyranne, M. Sviridenko. Approximation algorithms for shop scheduling problems with minsum objective. J. Scheduling 5:287--305, 2002.

Crossref

Google Scholar

[12]

R. L. Rivest, A. Shamir, L. M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2):120--126, 1978.

Digital Library

Google Scholar

Cited By

View all

Hug DPetralito SHauser SLamprou ARepenning ABertschinger DStüber NCslovjecsek MFazekas GBarthet MStockman T(2017)Exploring Computational Music Thinking in a Workshop Setting with Primary and Secondary School ChildrenProceedings of the 12th International Audio Mostly Conference on Augmented and Participatory Sound and Music Experiences10.1145/3123514.3123515(1-8)Online publication date: 23-Aug-2017
https://dl.acm.org/doi/10.1145/3123514.3123515
Kortsarts YKempner YLapidot TGal-Ezer JCaspersen MHazzan O(2012)Enriching introductory programming courses with non-intuitive probability experiments componentProceedings of the 17th ACM annual conference on Innovation and technology in computer science education10.1145/2325296.2325330(128-131)Online publication date: 3-Jul-2012
https://dl.acm.org/doi/10.1145/2325296.2325330

Index Terms

Teaching the power of randomization using a simple game
1. Social and professional topics
  1. Professional topics
    1. Computing education
      1. Computing education programs
        Computer science education

Recommendations

Teaching the power of randomization using a simple game

Any deterministic algorithm can be viewed as a game between the algorithm player and the input player. A randomized algorithm can be viewed as a mixed strategy for the first player, used to minimize the disadvantage of being the first to reveal its ...
Partially effective randomization in simulations between arbitrary and common PRAMs

It is known that Θ(log n/log log n) steps are needed to simulate one step of ARBITRARY CRCW PRAMs by COMMON CRCW PRAMs, but it was open whether there is a faster simulation when randomization is allowed. This paper gives both positive and negative ...
The impact of randomization in smoothing networks

We revisit randomized smoothing networks (Herlihy and Tirthapura in J Parallel Distrib Comput 66(5):626---632, 2006), which are made up of balancers and wires. We assume that balancers are oriented independently and uniformly at random. Tokens arrive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGCSE '06: Proceedings of the 37th SIGCSE technical symposium on Computer science education

March 2006

612 pages

ISBN:1595932593

DOI:10.1145/1121341

Program Chairs:
Doug Baldwin
SUNY Geneseo
,
Paul Tymann
Rochester Institute of Technology
,
Susan Haller
SUNY Potsdam
,
Ingrid Russell
University of Hartford

ACM SIGCSE Bulletin Volume 38, Issue 1
March 2006
553 pages
ISSN:0097-8418
DOI:10.1145/1124706
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: 03 March 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCSE06

Sponsor:

SIGCSE06: Technical Symposium on Computer Science Education

March 3 - 5, 2006

Texas, Houston, USA

Acceptance Rates

Overall Acceptance Rate 1,595 of 4,542 submissions, 35%

Upcoming Conference

SIGCSE TS 2025

Sponsor:
sigcse

The 56th ACM Technical Symposium on Computer Science Education

February 26 - March 1, 2025

Pittsburgh , PA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
319
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hug DPetralito SHauser SLamprou ARepenning ABertschinger DStüber NCslovjecsek MFazekas GBarthet MStockman T(2017)Exploring Computational Music Thinking in a Workshop Setting with Primary and Secondary School ChildrenProceedings of the 12th International Audio Mostly Conference on Augmented and Participatory Sound and Music Experiences10.1145/3123514.3123515(1-8)Online publication date: 23-Aug-2017
https://dl.acm.org/doi/10.1145/3123514.3123515
Kortsarts YKempner YLapidot TGal-Ezer JCaspersen MHazzan O(2012)Enriching introductory programming courses with non-intuitive probability experiments componentProceedings of the 17th ACM annual conference on Innovation and technology in computer science education10.1145/2325296.2325330(128-131)Online publication date: 3-Jul-2012
https://dl.acm.org/doi/10.1145/2325296.2325330

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

Index Terms

Recommendations

Teaching the power of randomization using a simple game

Partially effective randomization in simulations between arbitrary and common PRAMs

The impact of randomization in smoothing networks