CS 311 Fall 2007  >  Final Exam Review Problems, Part 1

CS 311 Fall 2007
Final Exam Review Problems, Part 1

This is the first of four sets of review problems for the Final Exam. A complete review for the final includes the material of the Midterm Exam as well, which is covered in three problem sets posted earlier in the semester. For all seven sets, see the the class web page, or the following links:

Final Exam Information

The Final Exam will be given on Monday, December 17, 1–3 p.m. It will be worth 100 points. The exam will be comprehensive, emphasizing the material covered after the Midterm Exam.

Referring to books, electronic devices, or other people during the exam will not be permitted. Limited use of notes will be permitted; see the “Cheat Sheet” section, below.

“Cheat Sheet”

Students will be allowed to bring one sheet of handwritten notes (a “cheat sheet”) to the Final Exam. Notes brought to the final must conform to the following guidelines, which will be ruthlessly enforced.

  1. You may bring no more than one sheet of notes; both the front and the back may be used.
  2. Notes must be on paper no larger than standard notebook paper (U.S. letter [8.5" x 11"], U.S. Legal [8.5" x 14"], or ISO A4 [210 mm x 297 mm])
  3. Notes must be handwritten. In particular, the following are prohibited: photocopies (including photocopies of handwriting), computer-printed pages, pages from books, typewritten notes, photographs.

Problems

Review problems are given below. Answers are in the Answers section of this document. Do not turn these in.

    1. Briefly explain how the Introsort algorithm works.
    2. What is the order of Introsort?
    3. What is the major advantage of Introsort, over other sorting algorithms?
    4. List four important disadvantages of Introsort, compared with other sorting algorithms?

     
    1. What kinds of data does the Radix Sort algorithm work on?
    2. Briefly explain how Radix Sort works.

     
    1. What is “abstraction”?
    2. What does “ADT” stand for, and what does it mean?

     
  4. Name two possible data structures that one might use to implement ADT Sequence (or a similar ADT). Briefly discuss advantages and disadvantages of each.
     
    1. ADTs Sequence and SortedSequence are superficially similar. However, they have an important fundamental difference. Explain. (Hint: What kind of ADT is SortedSequence?)
    2. When we put a list of items in order, we often do not care what the order is. Explain.
    3. What kinds of data are SortedSequence and ADTs like it used for? (Hint: There are two big categories of applications.)

     
    1. What does it mean for an interface to be “complete”? Give an example of an interface that is not complete.
    2. Give an example of an interface that does not facilitate efficiency.
    3. Give an example of an interface that is not very generic.

     
    1. List the three standard levels of exception safety, and briefly describe each.
    2. Which level do we usually prefer? Briefly explain why we prefer it.

     
  8. List two circumstances in C++ programming in which it is important to offer the No-Throw Guarantee. For each, briefly explain why this guarantee should be offered.
     
    1. We can write a good copy assignment operator for a class even if we know next to nothing about the class. Explain.
    2. If certain member functions in our class have certain properties, then our copy assignment operator (written as in the previous part) is exception-safe. What properties do these functions have to have, and what level of exception safety does our copy assignment operator have?

     
    1. Explain the difference between constant time and amortized constant time.
    2. What kinds of operations on sequences are typically constant time?
    3. What kinds of operations on sequences are typically amortized constant time (without being constant time)?

     
    1. What is a “generic container”?
    2. What language construct do we usually use to implement generic containers in C++?
    3. How does the use of this construct change our normal source/header file setup?

     
    1. How do generic containers complicate exception safety?
    2. What is “exception neutrality”?
    3. Suppose we use an operation on a client-specified type, and this operation may throw. If we want to be exception-neutral, how should we handle this (what should the code look like)?

     
  13. Give a reason for the rule that every function should have exactly one purpose (that is, it should do “one thing”).
     
    1. What do we mean by a “node-based structure”?
    2. List some advantages that node-based structures have over (smart) arrays.
    3. List some disadvantages.
    4. List several data structures that are often implemented using the node/pointer idea.

     
  15. When we implement a node-based structure using a C++ class, we usually write several classes. List and explain these (at least three).
     
    1. How are ownership issues typically handled in a node-based structure?
    2. How does this affect the design of the destructors for classes related to a node-based structure?

     
    1. In the context of Linked Lists, what does it mean to “splice”?
    2. “Splicing is what makes Linked Lists worthwhile.” Explain (even if you do not agree with the statement :-).
    3. How does the possibility of splicing affect the efficiency of computing the size of a Linked List?

     
    1. What is “locality of reference”?
    2. How is locality of reference related to memory caching and data-structure design?
    3. Briefly discuss locality-of-reference and caching issues with std::vector, std::deque, and std::list.

     
    1. List five operations or algorithms for which the orders differ for (smart) array-based sequences and Doubly Linked Lists. Give the order of each operation.
    2. List five operations or algorithms for which the orders are the same for (smart) array-based sequences and Doubly Linked Lists. Give the order of each operation.

     
  20. Suppose we are implementing a Singly Linked List.
    1. What data members do we generally want in the class representing the entire list?
    2. What data members do we generally want in the node class?
    3. How would the above change for a doubly linked list?

     

Answers

    1. Introsort is essentially Quicksort with median-of-three pivot selection. In addition, it keeps track of the recursion depth. If this exceeds some bound (perhaps 2log2n?), the algorithm switches to Heap Sort for the given recursive call. Usually, standard optimizations for Quicksort are used: tail-recursion elimination for the larger recursive call, and maybe a final pass with Insertion Sort.
    2. Introsort is log-linear time.
    3. Introsort is generally considered to be the fastest known sorting algorithm.
    4. On the downside, Introsort is not stable, requires random-access data, uses significant extra space (logarithmic), and nearly sorted data does not improve its performance.
    1. Radix Sort sorts lists of strings (positive integers may be considered as strings of digits, if padded on the left with zeroes).
    2. Radix Sort proceeds in a number of passes. Each pass uses a Pigeonhole Sort to sort the list by one of the characters in each string. The first pass sorts by the least-significant character. The second pass sorts by the next-to-least-significant character, and so on, with the last pass sorting by the most-significant character.
    1. Abstraction means separating the purpose of a module from its implementation. That is, we specify interface and effects, without specifying internal implementation.
    2. An ADT is an Abstract Data Type, that is, a collection of data together with some operations defined on that data.
  4. One might implement a Sequence using:
    1. Sequence is a position-oriented ADT, in which we deal with items primarily by their position in the container. SortedSequence is a value-oriented ADT, in which we deal with items primarily by their values.
    2. When we put items in order, it is often not because we want them in that order, but because we want them to be easy to find (think “Binary Search”). Thus, we do not care what the order is, only that it makes searching fast.
    3. Value-oriented ADTs like SortedSequence are used for
      • “Set” data. Data for which we only care whether an item is in the container, not where it is.
      • “Table” data. We use value-oriented ADTs to handle key-based look-up. Other names for such structures: dictionaries, maps, associative arrays.
    1. An interface is complete if all desired operations on the data can be performed using only the interface. A simple example of an incomplete interface would be a Stack with push, but no pop.
    2. One example is the text’s ADT List, especially if implemented using an array. Arrays allow constant-time modification of data in-place. However, using List, to modify an item we must first delete the old item and then insert a new one. With an array implementation, these are both linear-time operations.
    3. One example would be a Sequence-style interface that requires the data to be integers. There iss no particular reason for this to be the case.
    1. The three standard levels of exception safety are as follows:
      Basic Guarantee
      Data remain in a usable state, and resources are never leaked, even in the presence of exceptions.
      Strong Guarantee
      If an operation throws an exception, then it makes no changes that are visible to the client.
      No-Throw Guarantee
      The operation never throws an exception.
    2. We generally prefer the Strong Guarantee. We do not prefer the Basic Guarantee, since it means that, when an exception is thrown, objects may end up in unknown (but valid!) states. With the Strong Guarantee, we always know what state an object will be in. On the other hand, we do not prefer the No-Throw Guarantee, since it limits our options for flagging an error. The Strong Guarantee allows us to use exceptions, while the No-Throw Guarantee does not.
  8. It is important to offer the No-Throw Guarantee:
    1. If the class has a copy constructor and a swap member function (declared in the usual way), then we can write a copy assignment operator that uses them. The copy assignment operator uses the copy constructor to create a copy of a given object, and then uses the swap function to swap the value of the copy with its own value. The code is as follows (“Foo” is the name of the class): 
      Foo & operator=(const Foo & rhs)
{
    if (this != &rhs)
        Foo(rhs).swap(*this);
    return *this;
}
    2. The copy constructor needs to offer the Basic Guarantee (as everything should), and the swap function needs to offer the No-Throw Guarantee. If these are both the case, then our copy assignment operator offers the Strong Guarantee.
    1. An operation is constant time if its time order is O(1); that is, if it takes O(1) time to complete a single operation. An operation is amortized constant time if takes O(k) time to complete k operations. Thus, for an amortized constant time operation, the average time for a single operation, taken over a large number of consecutive operations, is O(1).
    2. Constant-time operations include look-up by index in an array and accessing the first item in pretty much any kind of sequence.
    3. The quintessential amortized-constant-time operation is insert-at-end for a smart array. This is a linear-time operation, since it may require reallocating and copying the entire array. However, in a well-written implementation, realocate-and-copy will not happen very often.
    1. A generic container is a container that can hold items of a client-specified type.
    2. In C++ we generally implement a generic container using a class template.
    3. The C++ Standard does not require compilers to be able to do separate compilation of templates. Thus, when we write a class template, we generally put all the code in the header file, with no source file at all.
    1. Generic containers use value-type operations to deal with the data they hold. These operations may throw exceptions that the generic container does not know about; but it still must be able to deal with them properly.
    2. Code is exception-neutral if, when an exception is thrown by a function the code uses, the exception is propagated unchanged to the client. Code for generic containers generally needs to be exception-neutral.
    3. When we write exception-neutral code, we deal with operations that may throw in one of two ways:
      • We use such operations outside any try block, thus automatically propagating the exception to the caller.
      • We use such operations inside a try block. In the associated catch block, we catch all exceptions, do whatever clean-up is necessary, and then re-throw the same exception.
  13. Here are two possible answers.
    1. A node-based structure is a data structure whose data items are stored in small memory blocks (often separately allocated), called nodes. Nodes typically reference each other via pointers.
    2. Node-based structures generally offer:
      • Faster rearrangement (insert, delete, and more complex operations).
      • More variety (tree-shaped structures, etc.).
      • Memory management that is more appropriate for some situations. Memory does not need to be allocated in a large block, and so the reallocate-and-copy operation that can slow down smart arrays never needs to happen.
    3. (Smart) arrays generally offer:
      • Faster position-based look-ups (e.g., “arr[i]”).
      • Less memory-management overhead, overall.
      • Simpler implementation.
    4. All of the following:
      • Linked lists (including doubly linked lists).
      • Just about any tree structure (except a Heap):
        • Binary Trees.
        • 2-3 Trees.
        • 2-3-4 Trees.
        • Red-Black Trees.
        • AVL Trees.
        • B-Trees.
        • Quadtrees.
        • Octrees.
      • Some Hash Tables (buckets can be node/pointer-based).
      • The C++ STL’s std::deque uses pointers to nodes that are small arrays.
  15. Classes needed:
    1. Each node object typically owns the nodes it points to. The object representing the structure as a whole typically owns the root node (or something similar).
    2. The destructor for each object only needs to delete pointers to nodes it owns. A typical destructor is thus one or two lines, with each line being a delete statement.
    1. Splicing is removing a subsection (consisting of consecutive items) from one list and inserting it into another list.
    2. Splicing is a constant-time operation for linked lists. It is not constant time for any of the other data structures we studied. Thus, splicing is where linked lists shine.
    3. If we do not allow splicing, then every linked-list operation changes the size of the list by at most 1 (or sets the size to zero). Thus, we can easily keep track of the size, and return it in constant time. However, splicing changes the size of a list by an amount that cannot be efficiently determined. Thus, if we allow splicing, then to determine the size of a linked list, we must iterate through it, a linear-time operation.
    1. Locality of reference is a property that an algorithm can have. It means that, when the algorithm access an item in a data structure, the following accesses are likely to be to the same item or nearby items.
    2. When a memory location is accessed, a memory cache will generally load nearby memory locations, thus greatly speeding up access to them. If an algorithm has locality of reference, it is thus advantageous to use a data structure in which consecutive items are stored in nearby memory locations.
    3. std::vector and std::deque tend to store consecutive items in nearby memory locations. Thus, when they are used with algorithms having good locality of reference, memory caching gives a significant performance boost. std::list generally does not store consecutive items in nearby memory locations. Thus, there is no associated performance boost.
    1. Here are seven for which the order differs:
      • Look-up, given index. O(1) for array; O(n) for doubly linked list.
      • Insert, given iterator. O(n) for array; O(1) for doubly linked list.
      • Insert at beginning. O(n) for array; O(1) for doubly linked list.
      • Insert at end. O(n) [amortized constant time] for array, unless provisions have been made for avoiding reallocation; O(1) for doubly linked list.
      • Remove, given iterator. O(n) for array; O(1) for doubly linked list.
      • Remove at beginning. O(n) for array; O(1) for doubly linked list.
      • Binary Search. O(log n) for array; O(n) for doubly linked list.
    2. Here are nine for which the order is the same:
      • Traverse (iterate through all items). O(n) for both.
      • Copy entire sequence. O(n) for both.
      • Swap two sequences. O(1) for both.
      • Sort. O(n log n) for both.
      • Retrieve first item. O(1) for both.
      • Retrieve last item. O(1) for both.
      • Create empty data structure. O(1) for both.
      • Remove at end. O(1) for both.
      • Sequential Search. O(n) for both.
    1. In a Singly Linked List class, the data members needed are:
      • A pointer to the first node in the list (head pointer).
      • Maybe the size of the list.
    2. In a Singly Linked List node class, the data members needed are:
      • This node’s data item.
      • A pointer to the next node in the list.
    3. In a Doubly Linked List, the class needs two pointers (head & tail), and the node needs two pointers (next & previous).

CS 311 Fall 2007: Final Exam Review Problems, Part 1 / Updated: 12 Dec 2007 / Glenn G. Chappell / ffggc@uaf.edu Valid HTML 4.01!