From specific problem instances to algorithms in the introductory course

ABSTRACT

In this paper, we present an approach for the introduction of problem solving and algorithm development in the first computer science course. Our technique is a more formal and systematic approach to programming based on generalizing a pattern after studying and expanding on a sequence of specific problem instances. In our approach, the algorithm and justification of its correctness are developed together.

REFERENCES

• 1: Owen Astrachan, Pictures as invariants, Proceedings of the twenty-second SIGCSE technical symposium on Computer science education, p.112-118, March 07-08, 1991, San Antonio, Texas, United States
• 2: William J. Collins, The trouble with for-loop invariants, Proceedings of the nineteenth SIGCSE technical symposium on Computer science education, p.1-4, February 25-26, 1988, Atlanta, Georgia, United States
• 3: Edsger W. Dijkstra , W. H. Feijen, A Method of Programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 4: David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 5: David Gries, Teaching calculation and discrimination: a more effective curriculum, Communications of the ACM, v.34 n.3, p.44-55, March 1991 [doi>10.1145/102868.102870]
• 6: Peter B. Henderson, Discrete mathematics as a precursor to programming, Proceedings of the twenty-first SIGCSE technical symposium on Computer science education, p.17-21, February 1990, Washington, D.C., United States
• 7: Barry L. Kurtz , J. Mack Adams, Using concept expansion and level integration in an introductory computer science course, Proceedings of the nineteenth SIGCSE technical symposium on Computer science education, p.244-248, February 25-26, 1988, Atlanta, Georgia, United States
• 8: Udi Manber, Using induction to design algorithms, Communications of the ACM, v.31 n.11, p.1300-1313, Nov. 1988 [doi>10.1145/50087.50091]
• 9: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 10: P. Montague. A correctness proof for binary search. Computer Science Education, 2(1):81-89, 1991.
• 11: Wing C. Tam, Teaching loop invariants to beginners by examples, Proceedings of the twenty-third SIGCSE technical symposium on Computer science education, p.92-96, March 05-06, 1992, Kansas City, Missouri, United States
• 12: Allen B. Tucker , W. James Bradley , Robert D. Cupper , David K. Garnick, Fundamentals of computing I: logic, problem solving, programs, and computers, McGraw-Hill, Inc., New York, NY, 1991

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Computer science education

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Methodologies**

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Human Factors, Languages