Exam 1 Topics and Practice Problems
CSSE 221 – Fundamentals of Software Development Honors
Fall 2008–2009

Exam format

• The exam is closed-book, closed-notes, except that you may bring a 3x5 index card with whatever you want on it (handwritten, typed, xeroxed, whatever, on both sides).
• The exam is designed to take less than 1 hour, although you may start as much an hour early and stay as much as an hour late.
• The exam is paper-and-pencil; no computer is needed or allowed.
• This document lists at least 95%, and perhaps 100%, of the topics on this exam.
• The points listed for each item indicate approximately how many points of the exam (out of 100 points) will be devoted to that topic.

Exam topics and Practice problems

1. [5 points] The definition of big-Oh. Be able to repeat the definition, substituting particulars for f and g as required.

   1. Sample problem: According to the definition of big-Oh, what does it mean when you say T(r) is O(r³)?

2. [8 points] Determining the big-Oh class for a given function, by using shortcut rules.

   1. Sample problem: Fill in the blank in the most appropriate way: 7n^1.5 + 25n² log n + 37n + 703 is O(____________).

3. [8 points] Determining the big-Oh class for the run-time of a given block of nested loops.

   1. Sample problem: What is the run-time of the following code snippet, in terms of n?

      	for (int k = 5; k < 2 * n; ++k) {
      	    for (int j = 0; j < k; ++j) {
      	        System.out.println("hello");
      	    }
      	    for (int j = 0; j < n; ++j) {
      	        System.out.println("hello");
      	    }
      	    for (int j = 0; j < k; ++j) {
      	        System.out.println("hello");
      	    }
      	}
      

4. [20 points] Determining the big-Oh class for the run-time of a given operation on a given data structure.

   1. Sample problem: What is the run-time of adding an element to the beginning of a linked list, if the list has n elements?
   2. Sample problem: What is the run-time of traversing (i.e., iterating through) an ArrayList, if the list has m elements?

5. [5 points] The Java Collections Framework: What is it, why use it?.

   1. Sample problem: The Java Collections Framework has three aspects. What are they?
   2. Sample problem: List at least three reasons for using the Java Collections Framework.

6. [5 points] Interfaces in the Java Collections Framework.

   1. Sample problem: What is the role of interfaces in the Java Collections Framework, as opposed to implementations and algorithms?
   2. Sample problem: The Java Collections Framework has 7 interfaces. List their names.
   3. Sample problem: In 20 words or fewer, what is the Queue interface?

7. [20 points] Choosing an interface and implementation in the Java Collections Framework.

   1. Sample problem: What is the role of interfaces in choosing a data structure for an application? What is the role of implementations in choosing a data structure for an application?
   2. Sample problem: Consider the four core interfaces, Set, List, Queue, and Map, as described in the Java Tutorial's Collections Trail at:

      	http://java.sun.com/docs/books/tutorial/collections/index.html"
      

      For each of the following four assignments, specify which of the four core interfaces is best suited, and explain how to use it to implement the assignment. Don't actually DO the assignment -- just state which interface (Set, List, Queue or Map) you would use and (in a sentence or less) why.

      • Whimsical Toys Inc (WTI) needs to record the names of all its employees. Every month, an employee will be chosen at random from these records to receive a free toy.
      • WTI has decided that each new product will be named after an employee — but only first names will be used, and each name will be used only once. Prepare a list of unique first names.
      • WTI decides that it only wants to use the most popular names for its toys. Count the number of employees who have each first name.
      • WTI acquires season tickets for the local lacrosse team, to be shared by employees. Create a waiting list for this popular sport.

   3. Sample problem: How do you decide whether to use the ArrayList or LinkedList implementation of List for your application?

8. [5 points] Implementations in the Java Collections Framework.

   1. Sample problem: What is the role of implementations in the Java Collections Framework, as opposed to interfaces and algorithms?
   2. Sample problem: What are two classes in the Java Collections Framework that implement List?

9. [10 points] Contiguous versus non-contiguous implementations of a List.

   1. Sample problem: Draw a picture that shows a contiguous implementation of a List. Then draw a picture that shows a non-contiguous implementation of a List.
   2. Sample problem: What is the main advantage of a contiguous implementation of a List over a non-contiguous implementation? What is the main advantage of a non-contiguous implementation of a List over a contiguous implementation?

10. [10 points] Implementing a linked list.

    1. Sample problem: Draw a picture that shows a linked list. Then show how the picture changes to:

       • Add an element to the front of the list.
       • Remove the last element of the list.
       • Add an element to the middle of the list.

    2. Sample problem: What is a recursive data structure? Give an example of a recursive data structure.
    3. Sample problem: A linked list must contain a recursive structure. Suppose that recursive structure is called Node. What are the fields (types and meaningful names) of that recursive structure?

11. [4 points] Algorithms in the Java Collections Framework.

    1. Sample problem: What is the role of algorithms in the Java Collections Framework, as opposed to interfaces and implementations?
    2. Sample problem: List three different algorithms provided in the Java Collections Framework.

Total: 100 points