article

On varying perspectives of problem decomposition

Author:

David GinatAuthors Info & Claims

ACM SIGCSE Bulletin, Volume 34, Issue 1

Pages 331 - 335

https://doi.org/10.1145/563517.563470

Published: 27 February 2002 Publication History

Get Access

Abstract

The most common decomposition perspective in computer science problem-solving is 'top-down', in which the problem at hand is divided into 'smaller' sub-problems. Yet there are more decomposition perspectives. In this paper we illuminate three additional perspectives and demonstrate their didactic value. The presentation is displayed in an apprenticeship manner, through different approaches for solving an intriguing algorithmic challenge - the problem of finding majority. Each of the three perspectives is tied to a variety of algorithmic problems and solutions, and elaborated as a pedagogical tool for teaching algorithms.

References

[1]

Boyer, R. S. and Moore, J S., A fast majority vote algorithm, Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Kluwer, Dordrecht, pp. 105-117, 1991 (the algorithm was invented in 1980).

Crossref

Google Scholar

[2]

Cormen, H. T., Leiserson, C. E., and Rivest, R. L., Introduction to Algorithms, MIT Press, Massachusetts 1991.

Digital Library

Google Scholar

[3]

Even, S., Graph Algorithms, Computer Science Press, 1979.

Digital Library

Google Scholar

[4]

Linn, M. C. and Clancy, M. J., The case for case studies of programming problems, Communications of the ACM, 35, 3, pp. 121-132, 1992.

Digital Library

Google Scholar

[5]

Maekawa, M., A sqrt(N) algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems,3, (2), pp. 145-159, 1985.

Digital Library

Google Scholar

[6]

Manber, U., Introduction to Algorithms - A Creative Approach, Addison-Wesley Pub, 1989.

Digital Library

Google Scholar

[7]

Misra, J. and Gries D., Finding repeated elements, Science of Computer Programming,2, pp. 143-152, 1982.

Crossref

Google Scholar

[8]

Pugh, W., Skip Lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33, pp. 668-676, 1990.

Digital Library

Google Scholar

[9]

Schoenfeld, A., Learning to think mathematically: problem solving, metacognition, and sense making in mathematics, Handbook of Research on Mathematics Teaching and Learning, pp. 334-370, Macmillan, 1992.

Google Scholar

Cited By

View all

Choppella VViswanath KKumar M(2021)Algodynamics: Algorithms as systems2021 IEEE Frontiers in Education Conference (FIE)10.1109/FIE49875.2021.9637441(1-9)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1109/FIE49875.2021.9637441
Pearce JNakazawa MHeggen S(2015)Improving problem decomposition ability in CS1 through explicit guided inquiry-based instructionJournal of Computing Sciences in Colleges10.5555/2831432.283145331:2(135-144)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.5555/2831432.2831453
Charitsis CPiech CMitchell JDoyle MStephenson BDorn BSoh LBattestilli L(2023)Detecting the Reasons for Program Decomposition in CS1 and Evaluating Their ImpactProceedings of the 54th ACM Technical Symposium on Computer Science Education V. 110.1145/3545945.3569763(1014-1020)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3545945.3569763
Show More Cited By

On varying perspectives of problem decomposition
1. Social and professional topics
  1. Professional topics
    1. Computing education
      1. Computing education programs

Recommendations

On varying perspectives of problem decomposition
SIGCSE '02: Proceedings of the 33rd SIGCSE technical symposium on Computer science education

The most common decomposition perspective in computer science problem-solving is 'top-down', in which the problem at hand is divided into 'smaller' sub-problems. Yet there are more decomposition perspectives. In this paper we illuminate three additional ...
Student perspectives on data provision and use: starting to unpack disciplinary differences
LAK '16: Proceedings of the Sixth International Conference on Learning Analytics & Knowledge

How can we best align learning analytics practices with disciplinary knowledge practices in order to support student learning? Although learning analytics itself is an interdisciplinary field, it tends to take a 'one-size-fits-all' approach to the ...
Chinese English Teachers' Perspectives on "Distributed Flip MOOC Blends": From BMELTT to BMELTE

This article reports on a study involving experienced university lecturers from mainland China reflecting on how to blend FutureLearn MOOCs into their existing English Language Teaching ELT curricula while on an 'upskilling' teacher education summer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGCSE Bulletin Volume 34, Issue 1

Inroads: paving the way towards excellence in computing education

March 2002

417 pages

ISSN:0097-8418

DOI:10.1145/563517

Issue’s Table of Contents

SIGCSE '02: Proceedings of the 33rd SIGCSE technical symposium on Computer science education
February 2002
471 pages
ISBN:1581134738
DOI:10.1145/563340
Conference Chairs:
Judith Gersting
University of Hawaii at Hilo
,
Henry M. Walker
Grinnell College
,
Program Chair:
Scott Grissom
Grand Valley State University

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: 27 February 2002

Published in SIGCSE Volume 34, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
608
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Choppella VViswanath KKumar M(2021)Algodynamics: Algorithms as systems2021 IEEE Frontiers in Education Conference (FIE)10.1109/FIE49875.2021.9637441(1-9)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1109/FIE49875.2021.9637441
Pearce JNakazawa MHeggen S(2015)Improving problem decomposition ability in CS1 through explicit guided inquiry-based instructionJournal of Computing Sciences in Colleges10.5555/2831432.283145331:2(135-144)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.5555/2831432.2831453
Charitsis CPiech CMitchell JDoyle MStephenson BDorn BSoh LBattestilli L(2023)Detecting the Reasons for Program Decomposition in CS1 and Evaluating Their ImpactProceedings of the 54th ACM Technical Symposium on Computer Science Education V. 110.1145/3545945.3569763(1014-1020)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3545945.3569763
Armoni MGal-Ezer J(2023)Computer Science Education Research in IsraelPast, Present and Future of Computing Education Research10.1007/978-3-031-25336-2_18(395-420)Online publication date: 18-Apr-2023
https://doi.org/10.1007/978-3-031-25336-2_18
Sooriamurthi R(2009)Introducing abstraction and decomposition to novice programmersACM SIGCSE Bulletin10.1145/1595496.156293941:3(196-200)Online publication date: 6-Jul-2009
https://dl.acm.org/doi/10.1145/1595496.1562939
Sooriamurthi RBrézillon PRussell ILabat J(2009)Introducing abstraction and decomposition to novice programmersProceedings of the 14th annual ACM SIGCSE conference on Innovation and technology in computer science education10.1145/1562877.1562939(196-200)Online publication date: 6-Jul-2009
https://dl.acm.org/doi/10.1145/1562877.1562939
Domanski L(2007)Slice and BlockwiseWell-Composed Sets6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007)10.1109/ICIS.2007.166(339-345)Online publication date: Jul-2007
https://doi.org/10.1109/ICIS.2007.166
Burns TKlashner RDeek F(2007)An empirical evaluation of a methodology‐tailoring information system development modelSoftware Process: Improvement and Practice10.1002/spip.35713:5(387-395)Online publication date: 4-Oct-2007
https://doi.org/10.1002/spip.357
Chinn D(2005)Peer assessment in the algorithms courseACM SIGCSE Bulletin10.1145/1151954.106746837:3(69-73)Online publication date: 27-Jun-2005
https://dl.acm.org/doi/10.1145/1151954.1067468
Chinn DCunha JFleischman WProulx VLourenço J(2005)Peer assessment in the algorithms courseProceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education10.1145/1067445.1067468(69-73)Online publication date: 27-Jun-2005
https://dl.acm.org/doi/10.1145/1067445.1067468
Show More Cited By

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

On varying perspectives of problem decomposition

Student perspectives on data provision and use: starting to unpack disciplinary differences

Chinese English Teachers' Perspectives on "Distributed Flip MOOC Blends": From BMELTT to BMELTE