CS173: Intro to Computer Science - Search Algorithms

Activity Goals

The goals of this activity are:
  1. To explain the role of an algorithm in computing
  2. To design an algorithm without the use of a computer

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Algorithms

Arrange yourselves in a line, and on a piece of paper, write down a whole number between 1 and N.

Questions

  1. Designate someone to go around the room, asking people what their number is. Write down how many steps that person needs, and what information they have at any given time. At each step, you can ask one person what their number is, and then you can ask if that is your number.
  2. How many steps did it take to find someone with the number you guessed?
  3. How many people are in the room? How might the number of steps change if you had room with more people in it?

Model 2: Algorithmic Efficiency

Arrange yourselves in a line, and on a piece of paper, write down a whole number between 1 and N. This time, arrange yourselves in increasing order by the number you've written down. This time, you can ask someone what their number is, and if their number is larger or smaller than the one you have.

Questions

  1. How many steps did it take to find someone with the number you guessed this time?
  2. How many people are in the room? How might the number of steps change if you had room with more people in it?
  3. Why is this approach better?
  4. What are the limitations of using this approach?

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.