**Instructions:** Work through the following problems and record your answers. On completion of your work, THEN access the Blackboard
System. Once you access Blackboard, you will NOT be able to back out to rework your answers.

**
A. Why is an algorithm that does 64n ^{2}+3n+10 steps of work on an input of size n considered to be of complexity
O (n^{2})?**

**
B. Write a general pseudocode algorithm to write out the contents
of an existing table i.e., to write each of the entries in the table, with
n ^{2} write operations being executed. Assume that the table is named
"A" and each row and column is of length "n"
**

243 |
187 |
314 |
244 |

215 |
420 |
345 |
172 |

197 |
352 |
385 |
261 |

340 |
135 |
217 |
344 |

C. Write a general pseudocode algorithm to write out n copies of the following table, so as to give one copy to each of the n district managers. Assume that the table is named "A" and each row and column is of length "n"

243 | 187 | 314 | 244 |

215 | 420 | 345 | 172 |

197 | 352 | 385 | 261 |

340 | 135 | 217 | 344 |

D. What is the order of magnitude of the work done by the algorithm of the previous question (C) if the unit of work of writing each element of the table is 1?

Use the following Bubble sort algorithm to answer the questions below:

Step 1: Set the marker (U) for the unsorted section at the end of the list

Step 2: Repeat steps 3-9

Step 3: Set the current element marker (C) on the second element of list

Step 4: Repeat steps 5-7

Step 5: If the element at C is less than the element to its left

Step 6: then Exchange these two items

Step 7: Move pointer C right one position

Step 8: Until pointer C is to the right of pointer U

Step 9: Move pointer U left one position

Step 10: Until unsorted section has only one element

Step 11: Stop

**
E. Perform a bubble sort on the following list: 4,8,2,6 and put the status of the list after the step 8 is executed in each of the iterations.
**

**I. If a list is already sorted in increasing order, a modified sequential search algorithm can be used that compares against each element in turn, stopping if a list element exceeds the target value. The following is the pseudocode
**

Step 1: Read values for target to be searched for, n, and the n list item

Step 2: I<-1, target not found

Step 3: Repeat steps 4 and 5 until either (target is found) or (I-th element > target) or (I>n)

Step 4: *-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Step 5: I<-I+1

Step 6: If target is not found, write "target not foundo/oo

Step 7: Stop

**
J. Examine the pattern matching algorithm as shown here: http://courses.cs.vt.edu/~cs1104/Algorithms/algorithm_25.htm. Given the string
AAAAAAAA, which of the following patterns will produce the worst case
(i.e., maximum number of comparisons)?
What is the general expression for the number of
comparisons in the worst case (i.e., how many comparisons will be
done in a general case, assuming the pattern is of length m and
the string is of length n)?
**

- Pattern: AAAB

- Pattern: AAAA

- Pattern: XXXB

**
K. Examine the pattern matching algorithm as shown here: http://courses.cs.vt.edu/~cs1104/Algorithms/algorithm_25.htm. Given the string
ABCDEFGH, which of the following patterns will produce the worst case?
What is the general expression for the number of comparisons in the worst case?
**

- Pattern: ABCD
- Pattern: AAAB

- Pattern: BCDE

- Pattern: XXXB

**L. For what input sizes n is an algorithm that does 50n units of work slower than an algorithm that does
2n ^{2} units of work? For what input sizes is it faster?
**

**M. What is the order of magnitude time complexity for the following
algorithm assuming step 1 is of order 1:
**

Step 1: Read C_{1},C_{2},...,C_{n}

Step 2: i <- 1

Step 3: Repeat steps 4 and 5 until i>n

Step 4: Write C_{i}

Step 5: i <- i+1

Step 1: Read C_{1},C_{2},...,C_{n}

Step 2: i <- 1

Step 3: j = n

Step 4: Write C_{i}

Step 5: i <- i+1

Step 6: C_{j}<- C_{i}

- Bubble sort
- Binary search
- Selection sort
- Sequential search
- Copy-over algorithm
- Converging-Pointers algorithm
- Pattern matching
- Exponential algorithm
- Insertion sort

**O. If you have a huge list of unordered names and need to search it (using as little computer time as possible) for a specific name, explain which of the list of algorithm(s) is the best suited if you just need to search the list once, and then have no use for the list again
**

**P. If you have a huge list of unordered names and need to search it (using as little computer time as possible) for a specific name,
which of the list of algorithm(s) is the best suited if you need to do such a search several times each work day.
**

When you have completed the answers on PAPER, then start the assignment