ACM SIGCSE 2013 Special Session: Engaging Mathematical Reasoning Exercises

Search Strategies: Hi-Lo Game

Clif Kussmaul, Muhlenberg College, kussmaul at muhlenberg.edu

Objectives

After completing this activity, learners should be able to:

• Explain the pros & cons of various simple search strategies.
• Explain common tradeoffs between the complexity and performance of algorithms.
• Assess the performance of simple algorithms as a function of their input size N.

Why Is It Engaging

• Based on familiar children’s game
• Students work in collaborative teams

Reasoning Topics Covered

• Search strategies
• Ways to measure and evaluate algorithms
• Tradeoffs (complexity vs. performance)

Audience

I use this the very first day of CS1, and often in CS2 as well
(depending how many of the CS2 students were in my CS1 class).
I can imagine expanding the activity for use in Data Structures.

Discussion (Difficulty, Strengths, Weaknesses, Dependencies, Variants)

• I like using this activity the first day of class because it shows:
  • how we (in CS) identify and evaluate ways to solve problems
  • common tradeoffs and their role in problem-solving
  • how CS can be a collaborative team activity.
• This is structured as a process-oriented guided inquiry learning (POGIL) activity,
  but I have used a similar structure to guide full class discussion with similar results.