CSSE 221: Fundamentals of Software Development Honors

Programming assignment

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. (15 pts) Weiss 6.5. I like this problem. You should write pseudocode for this answer. Pseudocode isn't graded for syntax, and can contain some explanation, but must contain enough details to easily translatable to Java.

2. (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…)
3. (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.
4. (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 Weiss Figure 5.11.
   1. 5
   2. 10
   3. 15
   4. 45
5. (3 pts) With an array of 1,000,000,000,000 elements, what is the maximum number of comparisons made with binary search?
6. (3 pts) We say that bubble sort is inefficient for large arrays. What do we mean, specifically, by "inefficient" sorting?
7. (3 pts) 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?
8. (4 pts) Explain the mergesort algorithm in your own words.
9. (5 pts) What is the best, worst and average case complexity of merge sort? Explain.
10. (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?)
11. 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.

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.

13. Answer the following:
    • Do students standing in the cafeteria line waiting to have their ID cards checked form a Stack or a Queue?
    • What would happen if students in that same line had to get their food using the other data structure?
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. Consider the following simple class used to control access to an integer.

    public class DataHolder {
    	private int data;
    	public DataHolder(int data) {
    		this.setData(data);
    	}
    	public int getData() {
    		return this.data;
    	}
    	public void setData(int data) {
    		this.data = data;
    	}
    }
    

    1. Rewrite it using generics.
    2. Declare and construct a DataHolder to hold the string "Bob" using the genericized class.
16. Prior to Java 1.5, there were no generics.
    • Say I wanted to rewrite the following code not using generics. I just take away the <String>, it won't compile. What else do I need to do? (Feel free to use your IDE to check this.)

      ArrayList<String> arr = new ArrayList<String>();
      arr.add("hello");
      String s  = arr.get(i);
      

    • Based on your answer to (a), explain briefly in your own words why using generics is advantageous.