CS 311 Fall 2008
Midterm Exam Review Problems, Part 3

This is the third of three sets of review problems for the midterm exam. For all three sets, see the class web page, or the following links:

• Part 1
• Part 2
• Part 3 (this document)

Problems

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

1. Algorithms faster than linear time are rare. Why?
    
2. One might think that, as computers get faster, we would not have to worry about efficient algorithms any more. And yet, your instructor mentioned this quote from Nick Trefethen.

   The fundamental law of computer science: As machines become more powerful, the efficiency of algorithms grows more important, not less.

   Explain the thinking that (probably) underlies this quote.
    
3. Is something missing from Design by Contract? For example, all stable sorting functions, whatever algorithm they use, would have the same preconditions and postconditions. If such functions all have the same description, then it seems we would have no reason to prefer one algorithm over the other. What useful/important information is missing from the “Design by Contract” description of a function?
    
4. 1. Insertion Sort is one of the slower sorting algorithms. Nonetheless, it is good for something. What is it good for?
   2. How does Insertion Sort work as part other algorithms?
   
    
5. 1. What is a “comparison sort”?
   2. Name a sorting algorithm that is not a comparison sort.
   
    
6. Explain the notation “Ω” and “&Theta” and their relationship to big-O.
    
7. In the context of algorithms, what is “divide-and-conquer”?
    
8. 1. Suppose an algorithm uses divide-and-conquer. It takes as input a list of size n. It splits this list into 3 pieces, and performs 3 recursive calls, each taking one of the pieces. In addition, the algorithm performs O(1) additional work. What is the order of this algorithm?
   2. Suppose the algorithm from part a instead does O(n) additional work. What is the order of the algorithm?
   Note: I do not expect you to have the Master Theorem memorized. If a question like this is on the midterm exam, then a statement of the Master Theorem will be provided.
    
9. 1. When using big-O, we generally do not write “O(log₂n)” or “O(log₁₀n)” or “O(ln n)”. Rather, we just write “O(log n)”. Explain.
   2. Under what circumstances do algorithms typically have a “log” in their order?
   
    
10. In each part, indicate the order of the given operation, using big-O. Use n to denote the length of the list. If no algorithm is specified, assume that a good algorithm is used.
    1. Printing the first element of an array.
    2. Printing every element of an array.
    3. Sequential Search on a list.
    4. Binary Search on a sorted array.
    5. Getting the value of item k in an array.
    6. Sorting an array.
    7. Sorting a linked list.
    8. Sorting an array with Quicksort.
    9. Sorting an array in which each item is at most 10 positions away from where it “should” be.
    
     
11. 1. Categorize each of the following sorting algorithms as O(n log n) or O(n²): Bubble Sort, Insertion Sort, Introsort, Merge Sort, Quicksort, Selection Sort.
    2. For one of the algorithms from part a, the category it goes in might be considered “surprising”. Which one, and why?
    
     
12. 1. What does it mean for a sorting algorithm to be “stable”?
    2. Characterize each of the following algorithms as stable or not (when written to maximize efficiency): Bubble Sort, Insertion Sort, Introsort, Merge Sort, Quicksort, Selection Sort.
    3. Stability is obviously a nice property for a sorting algorithm to have. Why, then, do many libraries implement a sorting algorithm that is not stable?
    
     
13. 1. There is no general-purpose comparison sort that lies in any time efficiency category faster than ... what?
    2. Briefly explain how we know that the answer to the previous part is true.
    3. Insertion Sort can sort a nearly sorted list in linear time. Explain why this fact does not contradict the answers to the previous parts.
    
     
14. Merge Sort is generally slower than Introsort. Why, then, is it preferred in some situations (give two reasons).
     
15. Quicksort with median-of-three pivot selection is a fine sorting algorithm for most data. Many people point out that the kind of data that makes this algorithm give poor performance, is extremely unlikely. And your instructor agrees with these people. Why, then, does your instructor say that using Quicksort is often a bad idea?
     
16. Suppose we analyze Quicksort using the Master Theorem. The input is split into two pieces [b = 2], two recursive calls are made [b^k = 2, and so k = 1], and linear-time extra work is done: pivot selection and partition [f(n) is O(n)]. Since f(n) is O(n^k), we are in case II, and so the algorithm is O(n^k log n), that is, log-linear time.

    But Quicksort is actually quadratic-time, not log-linear time. What is wrong with the above reasoning?
     

17. What important distinctions between arrays and Linked Lists do we need to consider when analyzing the efficiency of algorithms (for example, sorting algorithms) that deal with them?
     
18. Suppose we have the following declarations.

    class Foo {
    public:
        void nonConFunc();
        void conFunc() const;
    };
    
    Foo nonConObj;
    const Foo conObj;
    
    Foo * nonConPtr;
    const Foo * conPtr;

    In each part, indicate whether the give statement will compile. You may assume that all variables have been properly initialized.
    1. nonConObj.nonConFunc();
    2. nonConObj.conFunc();
    3. conObj.nonConFunc();
    4. conObj.conFunc();
        
    5. nonConPtr = nonConPtr;
    6. nonConPtr = conPtr;
    7. conPtr = nonConPtr;
    8. conPtr = conPtr;
        
    9. nonConPtr = &nonConObj;
    10. nonConPtr = &conObj;
    11. conPtr = &nonConObj;
    12. conPtr = &conObj;
    
     
19. 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?
    
     
20. 1. What kinds of data does the Radix Sort algorithm work on?
    2. Briefly explain how Radix Sort works.
    
     

Answers

1. Algorithms faster than linear time are rare, because an algorithm takes at least n steps to read all of its input. The only algorithms that can be faster than O(n) are those that do not need to read all of their input.
2. It is true that as computers get faster, problems that used to take a long time now take only a little time. However, we want to use our faster computers to solve bigger problems. An efficient, scalable algorithms is generally one that can take advantage of increased power to solve significantly bigger problems. And as problems get bigger, the advantages of efficient, scalable algorithms increase.
3. Two things are missing. First, Design by Contract says nothing about efficiency. In particular, for many functions, we need to specify their order, in addition to their pre- and postconditions, for them to be truly useful. Second, Design by Contract says nothing about requirements on types. When we do generic programming, pre- and postconditions are not a complete description of when a function can be used.
4. 1. Despite its slowness in general, Insertion Sort has very good performance on small lists. Insertion Sort is also fast [O(n)] for nearly sorted data: for example, data in which no item is more than some constant distance from where it needs to be, or data in which only a constant number of items are out of place.
   2. Well written sorting functions often switch to Insertion Sort when sorting small lists (with length less than 20, perhaps).

      Insertion Sort is also used as a finishing step in an optimized Quicksort. We write a recursive Quicksort so that it does nothing when given a small list. Calling such a function on a large list results in a nearly sorted list, which we can then finish sorting using insertion sort. This procedure is also used in Introsort, which is based on Quicksort.

5. 1. A comparison sort is a sorting algorithm that gets its information using a comparison function, which can compare any two items in the list to be sorted, and indicate which should come first.
   2. Two non-comparison sorts that we discussed are Pigeonhole Sort and Radix Sort. You may also have heard of Bucket Sort and Burst Sort.
6. We say g(n) is O(f(n)) if g(n) is at most some constant multiple of f(n), for sufficiently large values of n.

   For Ω, we replace “at most” with “at least”: we say g(n) is &Omega(f(n)) if g(n) is at least some constant multiple of f(n), for sufficiently large values of n.

   Finally, g(n) is &Theta(f(n)) if it is both O(f(n)) and &Omega(f(n)), that is, if it lies between two constant multiples of f(n), for sufficiently large values of n.

7. Divide-and-conquer is an algorithmic strategy. It means to split the input into parts and handle each part separately, often via recursion.
8. 1. We use the Master Theorem. The algorithm splits its input into 3 pieces. Thus, b = 3. It makes 3 recursive calls. Thus, b^k = 3, and so k = 1. It does O(1), that is, O(n⁰) extra work. And 0 < 1. Thus, we are in Case 1 of the Master Theorem. The order of the algorithm is O(n^k), that is, O(n).
   2. b and k are as before. Now we do O(n¹) extra work. And 1 = 1. Thus, we are in Case 2 of the Master Theorem. The order of the algorithm is O(n^k log n), that is, O(n log n).
9. 1. When we use big-O, we do not care about multiplication by a constant. For example, we do not write “O(20n)”, but rather “O(n)”; we can ignore the “20”. And a logarithm to one base is always a constant multiple of a logarithm to some other base. For example, log₁₀n = log₁₀2 × log₂n. Note that log₁₀2 is a constant. Thus, when using big-O, we can ignore the base of logarithms, and so we generally write logarithms without specifying a base.
   2. Algorithms with a “log” in their order [O(log n), O(n log n), etc.] are often those that use divide-and-conquer.
10. 1. O(1).
    2. O(n).
    3. O(n).
    4. O(log n).
    5. O(1).
    6. O(n log n). Use Merge Sort, Heap Sort, or Introsort.
    7. O(n log n). Use Merge Sort.
    8. O(n²).
    9. O(n). Use Insertion Sort.
11. 1. O(n log n): Introsort, Merge Sort. O(n²): Bubble Sort, Insertion Sort, Quicksort, Selection Sort.
    2. It might be surprising that Quicksort is O(n²) — the slower category — since for a long time many people considered it the fastest and best sort. However, although Quicksort has a terrible worst-case time, it has a very good average-case time. In the meantime, Introsort has surpassed it, and the issues above are now mostly moot.
12. 1. A sorting algorithm is stable if it does not reverse the order of equivalent items. (Two values are equivalent if neither is less than the other.)
    2. Stable: Bubble Sort, Insertion Sort, Merge Sort. Not stable: Introsort, Quicksort, Selection Sort. Note: Quicksort can be written in a stable form. However, doing this either greatly decreases its efficiency, making it less efficient than Merge Sort, on average. Thus, we generally do not consider Quicksort to be a stable sorting algorithm.
    3. Stability is nice, but speed is often nicer. The fastest sorting algorithms (e.g., Introsort) are not stable. Thus, some libraries include multiple sorting functions.
13. 1. There is no general-purpose comparison sort that lies in any time efficiency category faster than &Omega(n log n).
    2. There are n! possible orderings of n items. Since the result of any comparison cuts the number of possible orderings essentially in half, to determine which ordering is the correct one, we may need log₂(n!) comparisons, that is, Θ(n log n).
    3. We know that around n log n comparisons are needed in the worst case. Nearly sorted data are not the worst case for Insertion Sort. To put it another way, sorting only nearly sorted data is not “general”, in the sense of “general-purpose comparison sort”.
14. Merge Sort has two properties that Introsort does not have:
    • Merge Sort is stable.
    • Merge Sort works well with data that are not random-access.
    Thus, if stability is needed, or if data to be sorted are in a linked list or other sequential-access data structure, then Merge Sort is preferable to Introsort.

    Note: A third advantage of Merge Sort, which did not come up in the first half of the semester, is that its structure makes it work much better than Introsort with data accessed over a slow connection, for example data stored in a disk file.

15. Using Quicksort is often a bad idea for two reasons.
    • First, since the rise of the Web, malicious users have become increasingly common. Data that make certain algorithms exhibit poor performance may be unlikely to be generated at random, while being easy for a malicious user to generate.
    • Second, even randomly occuring poor performance is increasingly important. When a lone user is writing his own programs, he can probably handle occasional poor performance. But when the proper operation of software is critical to the operations of a company, government, etc., or perhaps a pacemaker, even occasional poor performance can be unacceptable.
    Lastly, we should note that the worst-case behavior of Quicksort is now easy to eliminate: use Introsort.
16. The Master Theorem only applies when the input is broken into nearly equal-sized parts. Quicksort does not necessarily do this.
17. There are two important distinctions between arrays and Linked Lists, when we deal with algorithmic efficiency.
    • Arrays are random-access. Given the index of an array item, we can find it quickly (constant time). In a Linked List, on the other hand, we must follow the chain of pointers (linear time).
    • Insertion and deletion of items in the middle of an array is slow (linear time). In a Linked List, however, once we have pointers to the appropriate nodes, we can insert and delete single items in constant time.
18. 1. Compiles.
    2. Compiles.
    3. DOES NOT COMPILE.
    4. Compiles.
    5. Compiles.
    6. DOES NOT COMPILE.
    7. Compiles.
    8. Compiles.
    9. Compiles.
    10. DOES NOT COMPILE.
    11. Compiles.
    12. Compiles.
19. 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 2log₂n?), 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.
20. 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.

CS 311 Fall 2008: Midterm Exam Review Problems, Part 3 / Updated: 17 Oct 2008 / Glenn G. Chappell / ffggc@uaf.edu