#### CS1104 Homework # 2

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 64n2+3n+10 steps of work on an input of size n considered to be of complexity O (n2)?

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 n2 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.

F. Perform a bubble sort on the following list: 12,3,6,8,2,5,7 and put the status of the list after step 8 is executed in each of the iterations.

G. Perform a bubble sort on the following list: D,B,G,F,A,C,E and put the status of the list after step 8 is executed in each of the iterations.

H. Explain why the bubble sort algorithm does O(n2) comparisons on an n-element list

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
Fill in the 4th step

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 2n2 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 C1,C2,...,Cn
Step 2: i <- 1
Step 3: Repeat steps 4 and 5 until i>n
Step 4: Write Ci
Step 5: i <- i+1
N. What is the order of magnitude time complexity for the following algorithm assuming step 1 is of order 1:

Step 1: Read C1,C2,...,Cn
Step 2: i <- 1
Step 3: j = n
Step 4: Write Ci
Step 5: i <- i+1
Step 6: Cj <- Ci

A list of algorithms for your consideration:
1. Bubble sort
2. Binary search
3. Selection sort
4. Sequential search
5. Copy-over algorithm
6. Converging-Pointers algorithm
7. Pattern matching
8. Exponential algorithm
9. 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