outline

Algorithm representation

• Natural language
  • too verbrose
  • too ambiguous
• Programming language
  • too detailed
  • syntax-oriented
• Pseudocode
  • compromise

Types of statements

• Computation
  • set the value of c to a + b => c = a + b
  • variables - storage locations for data
• Input
  • get values for a and b
• Output
  • print the value of c

Types of statements, cont'd

• Conditional
  • if [some true - false condition] then
  • first set of statements
  • else ( or otherwise)
  • second set of statements

Types of statements, cont'd

• Interative (looping)
  • Repeat until [true-false condition is true]
  • set of statements
  • While [true-false condition is true]
  • set of statments

Example 1

• 1) i = 1
  2) Repeat 3 to 5 until (i >10)
  3) i = i * i
  4) Print i
  5) J = i + 1

Example 2

• 1) i = 1
  2) While i <= 10 do
  3) i = i * i
  4) Print i
  5) i = i + 1
  
  i: 1 4 25

Two sides of the coin ...

• Repeat until count > 100
  • set of statements
  • presumably count increases in here
• While count <= 100
  • set of statements
  • presumably count increases in here

Search problem statement

• Input:
  • unordered list of items
  • target item to be searched for
• Desired output:
  • where item is found (or related data)
  • message if not found

First sequential search - p.38

• if NAME = first then print ans 1
• if NAME = second then print ans 2
• if NAME = third then print ans 3
• ...
• if NAME = 10000th then print ans 10000
• stop

This is very bad!

• Inefficient - keeps on going after finding NAME
• Wrong - doesn't say anything if value not found
• Too rigid - what if there are 10001 itemes to search? We must create a different algorithm to solve this closely related problem

2nd sequential search - p.39

• set i = 1 and found = false
• repeat until found is true
  • if NAME = 1-th then
  • print answer i
  • set found to true
  • else
  • increase i by one

This is even worse!

• What if NAME is not found?
• Sit no output; we keep searching
• i gets higher and higher
• Does not terminate

How do we fix things? - p.40

• Make sure we don't go off the deep end
• Add a test for valid data to the loop condition
• Repeat until found or i > 10000
• Then write output based on how we got out of the loop

Sequential search

• A better solution method is available if the list is ordered
• if the list is very long, sequential search can be very time consuming
• Imagine an unordered dictionary, an unoredered telephone book
• Ordering the list being searched is a way to structure the information