The Josephus Flavius' problem

ABSTRACT

You may have used the Josephus Problem as a programming assignment in one of your courses. I have been using this problem for many years in CS1 or CS2, primarily to illustrate applications of various data structures and algorithmic problem solving. The resulting "brute force" solution works, but is not elegant. Accordingly, I challenge students to analyze the problem more mathematically and use mathematical thinking to seek a more precise solution. Few students are successful. However, computer science students should develop the skills necessary to find both solutions, algorithmic and mathematical model. The latter provides an efficient solution that can be used to validate the algorithmic solution -- very important for critical systems components.

REFERENCES

• 1: <blue.butler.edu/~phenders/InRoads>
• 2: <blue.butler.edu/~phenders/???>
• 3: <http://www.cut-the-knot.org>
• 4: Moshe Augenstein , Aaron Tenenbaum, Program efficiency and data structures, ACM SIGCSE Bulletin, v.9 n.3, p.21-27, Aug 1977
• 5: Ball and Coexiter, Mathematical Recreations and Essays, Dover Publications, 13th Ed. (1987).
• 6: D. Woodhouse, Programming the Josephus problem, ACM SIGCSE Bulletin, v.10 n.4, p.56-58, December 1978 [doi>10.1145/988906.988919]
• 7: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994

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:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Design, Management