n301/Intro n301.tplt Chapter 1 What computer science is NOT: What CS is: Study of algorithms algorithm Why algorithms? If we can specify an algorithm, we can automate the solution The status of algorithms Some problems are unsolvable Some problems have no tractable solution > Some problems we don't know the algorithms 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"