n301/ Algorithms n301.tplt 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