Homework 23
CSSE 221 – Fundamentals of Software Development Honors
Fall 2008–2009

Recall the Due Dates and (from the syllabus) the Late (and early) Assignment Policy and guidelines for maintaining Academic Integrity.

Also recall that you can get help on any of these problems during the CSSE lab assistant hours, and you can use the Assignments Discussion Forum on Angel to discuss, clarify, or get help on these problems.

Things to do

1. Continue working on your Simulation project. Your team should have a UML class diagram and have begun implementing per your Iterative Enhancement Plan by now.
   • Reminder: Each team member must maintain and commit to the repository her coding statistics, as described in Coding statistics.
2. Complete your Sierpinski project.
   • Don't bang your head on the wall over the Sierpinski project!
   • If you aren't making clear progress after about 30 minutes, get help!
3. Do the written problems below.

Written problems

Write your answers to these questions. Turn your answers in via the appropriate Homework Drop Box on Angel.

1. Consider Insertion Sort. Here is an example of how insertion sort works on an array X.

   X:  13  94  10  17  12  35
   Step 1: Pick X[1], which is 94.  Insert it, working backwards, to get 13 94.
   Step 2: Pick X[2], which is 10.  Insert it into 13 94, working backwards, to get 10 13 94.
   Step 3: Pick X[3], which is 17.  Insert it into 10 13 94, working backwards, to get 10 13 17 94.
   Step 4: Pick X[4], which is 12.  Insert it into 10 13 17 94, to get 10 12 13 17 94.
   Step 5: Pick X[5], which is 35.  Insert it into 10 12 13 17 94, to get 10 12 13 17 35 94.
   Done.
   

   Here is the code for Insertion Sort:

       for(i=1; i < a.length; i++) {
           temp = a[i];
           j = i;
   
           while (j > 0 && temp < a[j-1]) {
               a[j] = a[j-1];
               j--;
           }
   
           a[j] = temp;
        }
   

   1. What is the worst-case run-time of insertion sort? Explain your answer. (NO credit if you have no explanation.)
   2. What is the best-case run-time of insertion sort? Explain your answer. (NO credit if you have no explanation.)