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
• >
• 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, if the amount of payment was
  adequate.  when the king asked Mathew
  about his requirements for compensation,
  Mathew responded that the king might
  choose between two options:

Complexity of Algorithms 2

• Option 1:
• One fifth of crops
• over following years, or

Complexity of Algorithms 3

• Option 2:
• One kernel of corn for first square of a chess board.
• Two kernals of corn for the second.
• four kernels for the third square
  (twice of previous square).
• eight for the fourth square (twice
  of previous square).
• ...and so on for all the 64 squares
  on the board.

Complexity of Algorithms 4

• The king considered these choices and
  decided to go with the second options.
  After all, how could a few kernels of
  corn compare with a fifth of the crops
  for five years!

• 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+22+23+24+25+26+27 or
  1+2+4+8+16+32+64+128=3D255 kernels of corn
  
  much less than a bushel and the king was
  smiling!
  For the next row, the payment was,
  28+29+210+211+212+213+214+215=3D65,280
  
  (a bushel of corn=3D72,800 kernels).  For the
  third row,
  216+217+218+219+220+221+222+223=3D963,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 263=3D8x1018 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"