Iambic IBM AI: the palindrome discovery AI project

ABSTRACT

In this paper, I describe an AI laboratory assignment in which students implement standard search techniques and explore heuristic measures of their own design for a palindrome discovery system. The system successfully derives palindromic sequences of words, many of which are meaningful, and achieves what is to the author's knowledge the first automatic generation of palindromes. Code is made available to students which implements the state space for palindrome search. This makes a large-scale problem accessible to introductory AI students by harnessing their knowledge of natural language. Students were motivated by the intrigue of discovering new palindromes.

REFERENCES

• 1: James R. Bitner , Edward M. Reingold, Backtrack programming techniques, Communications of the ACM, v.18 n.11, p.651-656, Nov. 1975 [doi>10.1145/361219.361224]
• 2: CELEX. The celex lexical database. CD-ROM, 1995. Centre for Lexical Information, Max Planck Institute for Psycholinguistics, Nijmegen.
• 3: Eleazar Eskin , Eric Siegel, Genetic programming applied to Othello: introducing students to machine learning research, The proceedings of the thirtieth SIGCSE technical symposium on Computer science education, p.242-246, March 24-28, 1999, New Orleans, Louisiana, United States
• 4: Greg A. Keim , Noam M. Shazeer , Michael L. Littman , Sushant Agarwal , Catherine M. Cheves , Joseph Fitzgerald , Jason Grosland , Fan Jiang , Shannon Pollard , Karl Weinmeister, Proverb: the probabilistic cruciverbalist, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.710-717, July 18-22, 1999, Orlando, Florida, United States
• 5: McCauley, R., and Manaris, B. Comprehensive report on the 1997 survey of departments offering csac/csab-accredited degree programs. Tech. rep., The Center for Advanced Computer Studies, University of Southwestern Louisiana, 1998.
• 6: McKeown, K. Text Generation. Cambridge University Press, New York, 1985.
• 7: Miller, G., Beckwith, R., Felbaum, C., Gross, D., and Miller, K. Introduction to WordNet: An online lexical database. Tech. rep., 1993.
• 8: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 9: Russell, S., and Norvig, P. A modern, agentoriented approach to AI instruction. In Proceedings of the AAAI Fall Symposium on Innovative Instruction for Introductory AI (New Orleans, Nov. 1994), AAAI Press.
• 10: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 11: Siegel, E. My home page (for the homewovk project, on-line palindrome system and results thereof). http://www.cs.columbia.edu/'evs/, 1999.
• 12: Eric V. Siegel, Why do fools fall into infinite loops: singing to your computer science class, Proceedings of the 4th annual SIGCSE/SIGCUE ITiCSE conference on Innovation and technology in computer science education, p.167-170, June 27-30, 1999, Cracow, Poland
• 13: Smadja, F., and MeKeown, K. Using collocations for language generation. Computational Intelligence 7, 4 (December 1991), 229-239.

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:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Algorithms, Design, Human Factors, Management, Performance, Theory