CSSE 221: Fundamentals of Software Development Honors

Miniproject deliverables (new!)

1. Problem statement and proposed solution: inalized documents should be in the repository.
2. Iterative Enhancement Plan (IEP) with requirements: please email your prof when you submit them to the repos.
3. Schedule: just add dates added to the IEP.
4. Task List: add your excel spreadsheet, containing the tasks you have already done and those are about to do, to the repos.

Programming assignment (due by Sunday, 9:00am)

Written homework to do before week 5 (due before beginning of class on Monday, Oct 2).

1. Read chapters 12.2 (MergeSort), 11.3 (BinarySearch) in Savitch, and the packet on databases handled out in class.
2. In *your own words*, explain clearly each of the following concepts:
   1. Database
   2. Transaction
   3. Query
   4. SQL
   5. JDBC
   6. Client
   7. Server
   8. Table
   9. Relational Database
3. Find at least one example of a database that you interact with on a regular basis (meaning at least a couple times a week) and tell us about it. Note: If you think that you don’t interact with any databases, then you are wrong!
4. Say I have an unsorted database (stored as an array) with n keys and am searching to see if an arbitrary element is in the database…
   1. What is the name of the search algorithm you would use?
   2. What is the worst-case number of comparisons it needs to make (in terms of n) to find it or say it’s not in the database? When does this happen?
   3. Express (b) using big-Oh notation.
   4. What’s the best-case number of comparisons it needs to make (in terms of n) to find it or say it’s not in the database? When does this happen?
   5. What’s the average-case number of comparisons it needs to make (in terms of n) if I know the element is in the database?
   6. Express (e) using big-Oh notation.
   7. Why can’t I ask you to find the average number of comparisons the algorithm would need to make to find arbitrary elements not known to be in the database? (This may be a bit subtle, just think…)
5. Repeat parts a-d of the previous question, only now assume that the database/array is sorted, so you should use a more efficient search algorithm.
6. With an array of 1,000,000,000 elements, what is the maximum number of comparisons made with binary search?
7. We say that bubble sort is inefficient for large arrays. What do we mean, specifically, by "inefficient" sorting?
8. The selection sort algorithm is still inefficient, but improves upon bubble sort in the number of swaps performed. How many swaps does it make for an array of size n?
9. Explain the mergesort algorithm in your own words.

10. What if we were sorting boxcars on the dock of a huge shipyard by a label on the outside of the car. In this case, comparisons (running back-and-forth and checking labels) are cheap compared to swaps (which require a heavy-duty crane).
    1. What if we had 20 boxcars? Justify your choice of which sort would be best in this case.
    2. What if we had 1,000,000 boxcars? (Not practical, of course, but how would you reason about this?)
11. Given the following list: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 perform a binary search for each of the following numbers and show all the comparisons you do to arrive at your answer. For example, in (a), the first comparison should be between 5 and 10. Use the code shown in Savitch, p. 674, assuming the search starts at first = 0, last = a.length.
    1. 5
    2. 10
    3. 15
    4. 45
12. What is the best, worst and average case complexity of merge sort? Explain.
13. What is the advantage of using prepared statements for many similar queries?