SUNY Geneseo Department of Computer Science

CS Methods of Inquiry

Previous Lecture

Misc

Mini-Assignments and Reading Summaries

• e-mailed comments before class OK

Interest survey

• CRN = 12257

Labs tomorrow, I'll hand out exercise there

Reading Summary

Chapter 1

Computer science = science of computing

Algorithms: pseudocode, computer language

Chilling time example

Methods of inquiry

• Design
• Theory
• Empirical analysis

Mini-Assignment and Game

The game

• I lay n cards in front of you.
• You have to find the one I consider "special", by selecting any subset of the cards and asking "is it in this subset?"
• I'll answer "yes" or "no"
• Your goal is to find the special card in as few questions as possible

What does this have to do with computer science?

Strategies for doing well in this game?

• First approach:
  • Try to narrow cards down in halves
  • (take away half with each question)
• This is an algorithm
• Another algorithm:
  • Guess a card randomly to narrow the cards down
• Coming up with these is design

Which algorithm will do better?

• Theory question
• Intuition: halving, because it removes as many cards as possible w/ each guess.
• But no chance of finding special card on first guess, whereas random card algorithm might
  • Best case vs worst case vs average case
• You expect this to measure time, i.e., that number of guesses can estimate time

Empirical analysis: e.g., confirm that in many real games, halving algorithm always requires no more guesses than random card algorithm

• (count guesses 'til answer is "yes")

Next

Introduction to algorithm design

Read Chap. 2 through Sec. 2.6

Mini-Assignment: Design an algorithm for the robot described in the book that makes the robot move forward until it comes to a wall.

Next Lecture