CSSE 221: Fundamentals of Software Development Honors

Optional Written Homework

This is an optional assignment (ignore the point values), consisting of more practice related to topics we have studied in the last few weeks. Doing it may help you review for the final exam. I will not collect it, but you may ask questions about it on the last day of class.

  1. (7 pts) Say I have an unsorted array with n elements and am searching to see if an arbitrary element is in the array…
    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 array? 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 array? 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 array?
    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 array? (This may be a bit subtle, just think…)
  2. (4 pts) Repeat parts a-d of the previous question, only now assume that the array is sorted, so you should use a more efficient search algorithm.
  3. (8 pts) 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 your text.
    1. 5
    2. 10
    3. 15
    4. 45
  4. (3 pts) With an array of 1,000,000,000,000 elements, what is the maximum number of comparisons made with binary search?
  5. (3 pts) You might think that selection sort isn't a great sort, but it actually performs fewer swaps than the others we've studied. How many swaps does it make while sorting an array of size n?
  6. (4 pts) Explain the mergesort algorithm in your own words.
  7. (4 pts) Write pseudocode for the merge operation (merging two sorted arrays into a single sorted array) in mergesort.
  8. (5 pts) What is the best, worst and average case complexity of merge sort? Explain.
  9. (10 pts) 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?)
  10. In the Java API (and many data structures books), adding a piece of data to a Stack is called "pushing" it on the Stack, and removing a piece of data from a Stack is called "popping" it off the Stack. For example, "push 12" means put the number 12 onto the top of the Stack; "pop" means remove the top item from the Stack.

    Draw a diagram of what a Stack for integer data would look like after the following commands:

    push 6
push 7
push 3
pop
push 4
push 4
push 15
pop
pop
pop

    Draw an arrow to the top of the Stack in your diagram.

  11. In the Java API, adding a piece of data to a Queue is called "offering", whereas removing a piece of data is called "polling" it. For example, "offer 6" means add the integer 6 to the end of the Queue; "poll" means remove the front item from the Queue.

    Draw a diagram of what a Queue for integer data would look like after the following commands:

    offer 6
offer 7
offer 3
poll
offer 4
offer 4
offer 15
poll
poll
poll

    Draw an arrow to the front of the Queue in your diagram.

  12. Answer the following:
  13. Implement a queue (enqueue, dequeue, peek) using two stacks.
  14. Notice in the Java API that a Queue is an interface, implemented by a number of other classes, one of which is a LinkedList.
    1. What is a good reason for using a LinkedList rather than some type of array?
    2. Write Java code to declare a Queue of integers, then add the integers 4,5, and 6 in turn, then remove the front of the Queue. (Use the API; don't re-implement Queues!)
  15. Review inheritance, polymorphism, and overloading/overriding functions.
  16. Consider the documentation for this strange method: 
    
/* If the input contains an even number of characters, it transforms it by swapping its case. If it contains an odd
 * number of characters, it transforms it by sorting the characters alphabetically.
 *
 * For example, strange("to be") yields " beot".
 *
 * @param input
 * @return a transformed string
 */
public static String strange(String input) {
// body code elided
}
    List pairs of inputs and expected outputs that would constitute a good test set for this method. For each argument you list, say briefly why it should be in the unit test.