SUNY Geneseo Department of Computer Science

Introduction to CS and Its Methods of Inquiry

Previous Lecture

Questions?

Computer Science's Methods of Inquiry

Chapter 1 reading summary

Central concern of CS is algorithms, which are well-defined processes for solving problems.

"Problems" have objectively recognizable solutions, and multiple instances.

CS Methods of inquiry are...

• Design, the planning of algorithms, programs, hardware, ...
• Theory, the mathematical modeling of algorithms, etc.
• Empirical analysis, the experimental testing of beliefs about algorithms, etc

Examples

"Find the special card" game.

• I lay out some playing cards, one of which is "special"
• You determine which card is special by asking yes-no questions about the cards
• Your goal is to find the special card in the fewest questions

Strategy (i.e., an algorithm)

• Ask a question that eliminates half the cards
• Continue until one card left

Problem? find special card per above rules

• Instance = specific set of cards

Another algorithm

• Pick a card
• Ask if it's the special card
• Continue until one card left

Do these algorithms always solve the problem? (Theoretical reasoning)

• First algorithm: reduces number of possible cards at each step, ....
  • Always solves problem in 3 or 4 steps
  • (Variation guaranteed to take 4 steps)
  • Generalization:
    • Suppose I had 256 cards, maybe takes 128 steps? or maybe 8?
    • Square root plus 1?
    • Really: the number of times you can halve number of cards (n) plus 1
      • e.g., 2^x cards means x + 1 questions
      • i.e., log₂(n) +1 questions
• What about 2nd algorithm? how many questions?
  • As many as 8? (because each question eliminates 1 card, but last question might be the "yes")
  • Generally, n questions in the worst case
  • Or 1 question in best case

But does this sort of analysis really matter, are the real-world running time differences enough to justify developing the more complicated but faster algorithm?

• Look at a real program that implements a word-counting algorithm in 2 ways, one theoretically faster than the other
• Small text (a few tens of words): slow algorithm took 125 mS, fast took 105 mS. So what?
• Real text ("War and Peace") slow algorithm took about 514 seconds, fast took 3. Yes, theoretical differences can matter in a very big way!
• (And this, by the way, was empirical analysis, albeit of an informal sort.)

Next

Design with Objects

Read Chapter 2

Next Lecture