SUNY Geneseo Department of Computer Science

Introduction

(No Previous Lecture)

Introductions

This is CSci 141, Introduction to Computer Science

I'm Doug Baldwin

Lab 1

Hand out Syllabus

Where this course fits

What is Computer Science?

Methods of inquiry

• Design
• Mathematical Theory
• Empirical Science

An illustration

• A searching-an-array game
  • I control the array:

• I will keep it in ascending order
• I reveal elements' values only as you ask for them
• You do the searching
  • Goal is to determine whether a particular value is in the array or not
  • You ask to see array elements one at a time, identifying them by position
• We both agree on the value you are seeking
• What are some strategies you could use to do the searching?
  • Binary search

            Ask about middle element
              if higher than what you want
                  repeat in first half
              if lower than what you want
                  repeat in upper half
              else
                  done

• Sequential search

            Check element 0
              then element 1
              then 2...
              until you either what find you want or get to end of array

• This was design
• How many questions do you have to ask?
  • This is theory
  • Binary search keeps halving the array with each question
  • e.g., 8 elements
    • Binary search takes at most 4 questions
    • Sequential takes at most 8 questions
  • What about n elements
    • Binary search is n/2?
    • Actually log₂n questions
• How long does playing the game really take?
  • Measure it
  • Data
    • Whole game: 20 seconds
    • Questions: 4, 5 ,5, 3 seconds
      • Average: 4.25
  • Sequential search might take about 34 seconds
  • This is experimentation

Next

A more thorough look at design in an object oriented setting

Read Chapter 2

Be prepared to play chess

Next Lecture