outline

Chapter 1

• What computer science is NOT:
  • Study of computers
  • Study of how to write programs
  • Applications programs
    • word processing, spreadsheets, etc.

What CS is:

• Study of algorithms
• algorithm
  • sequence of instructions to solve a problem

Why algorithms?

• If we can specify an algorithm, we can automate the solution
  • computing agent can carry it out
    • able to understand and perform instructions
  • human, robot, computer

The status of algorithms

• Some problems are unsolvable
  • no algorithmic solution
• Some problems have no tractable solution
  • "brute force" algorithms

The status of Algorithms 2

• Some problems we don't know the algorithms
  • many AI problems

Complexity of Algorithms

• Once upon a time a king needed a great task performed.
• In response, a clever young man named Mathew agreed to do the work

Complexity of Algorithms 2

• Mathew gave the king two options
• Option 1: One fifth of the crops the following years, or

Complexity of Algorithms 3

• Option 2:
• one kernel for the first square
• two kernals for the second.
• four kernels for the third square
• ...thus for all 64 squares

Complexity of Algorithms 3

• The king decided upon the second options.
• A year went by and Mathew finished his work and it was time for payment. The king
  ordered baskets of grain to be brought in
  and the counting began. For the first row
  of the chess board (eight squares), the
  payment was,
  

  1+2+2²+2³+2⁴+2⁵+2⁶+2⁷ or
  1+2+4+8+16+32+64+128=255 kernels of corn

  
  much less than a bushel and the king was
  smiling!
  For the next row, the payment was,
  

  2⁸+2⁹+2¹⁰+2¹¹+2¹²+2¹³+2¹⁴+2¹⁵=65,280

  
  (a bushel of corn=72,800 kernels). For the
  third row,
  

  2¹⁶+2¹⁷+2¹⁸+2¹⁹+2²⁰+2²¹+2²²+2²³=963,040,

  
  about 13 bushels of corn and the king was
  no more smiling. The counting continued,
  and for the 64th square alone, the payment
  was 2⁶³=8x10¹⁸ kernels or about 110,000
  billions bushels!! The king abdicated the
  throne, and the mathemativally sophisticated
  Mathew became the monarch of the kingdom.

Algorithm

• Origin of the Word Algorithm
• 1. This word DID NOT APPEAR in the Webster's New World Dictionary until 1957!
  2. An older form "ALGORISM" --- THE PROCESS OF DOING ARITHMATIC USING ARABIC NUMBERIALS.
  3. After Middle Ages --- ALGIROS(painful)+ARITHMOS(number) or King of Algor of Castille --- Guesses!
  4. ALGORISM -- From the name of a famous Persian textbook author --
     Abu Ja'far, Mohammed ibu Musa al-Khowarizmi (C.825)
     (Father of Ja'far, Mohammed son of Moses native of Khowarizm)
  5. ALGORISM is a corrupted version of ALGORISM
  6. Definition of the word ALGORITHMUS from an early German Mathematical Dictionary (1747):
     

     'Under this definition are combined the notions of four types of arithmetic calculations, namely, addition, multiplication, subtraction and division.'

  7. Modern Meaning of ALGORITHM: Similar to Recipe, Process, Method, Technique, Procedure, Routine,
     • Except Just a Little DIFFERENT:
       • Finiteness -- Termination
       • Definiteness -- Precision
       • Input -- Zero or More Inputs
       • Output -- One or More Outputs
       • Effectiveness -- Exactly and in Finite Length of Time by Paper-Pencil Method

Algorithm definition

• Well-ordered collection...
• of unambiguous and effectively computable operations...
• that produces a result...
• and halts in a finite amount of time

This is NOT an Algorithm!

• 1. Add flour until paste is sticky
  2. Knead until firm
  3. Roll thin and cut
  4. Bake in a medium oven until light brown
  5. Place on rack until cool

Also NOT an Algorithm!

• 1. Apply small amount of shampoo to hair
  2. Work into scalp for about 1 minute
  3. Rinse thoroughly
  4. Repeat

A good Example of an algorithm

• A recipe for cherry pie
  • Step1: Mix 1 cup sugar, 1/4 cup flour, 1/4 tsp. salt
  • Step 2: Stir in 1/2 cup juice from the cherries
  • Step 3: Cook & stir over medium heat until thick
  • Step 4: Add 3 cups canned, pitted red cherriesStep 6: Make pie crust & place in a 9 inch pie plate
  • Step 7: Fill crust with cherry mix & top with 2nd crust
  • Step 8: Bake at 450 for 10 min. then 350 for 45 min.

CS studies algorithms

• their formal and mathematical properties
• their hardware realizations
• their linguistic realizations
• their applications

Therefore, our task is to:

• design & develop algorithms to solve problems
• study the algorithms to see if they are correct and efficient
• design and build computer systems which can execute these algorithms
• "If we can specify an algorithms for a problem, then we ccan automate its solutions"