CS 311 Fall 2007
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. In each part, a formula is given for the approximate worst-case number of operations performed by some function when given input of size n. Write the order of each function using big-O. If there is an associated name for this order, give it.
   1. 500 + 30n.
   2. 500 + 30n + 2n³.
   3. 500 + 30n + 2 ln n.
   4. 500 + 30n + 2n log₂n.
   5. 500 + 30n + 2n² + 5n log₁₀n.
   6. 500.
   
    
2. In general, what are the slowest algorithms that actually get used?
    
3. Algorithms faster than linear time are rare. Why?
    
4. 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.
    
5. 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?
    
6. In our second implementation of Bubble Sort in class, we were careful to use only increment (++) on iterators, and never decrement (--). Why?
    
7. 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?
   
    
8. 1. Suppose we have a loop that is executed 3n–2 times. The body of the loop does a Binary Search on an array of size n. What is the order of this entire operation?
   2. Suppose we have a sorted array containing n integers. We find the sum of the integers. Then we find their product. Lastly, we do a Binary Search on them. What is the order of the combined operation?
   
    
9. In the context of algorithms, what is “divide-and-conquer”?
    
10. 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.
     
11. 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?
    
     
12. 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.
    
     
13. 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?
    
     
14. 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?
    
     
15. Merge Sort is generally slower than Introsort. Why, then, is it preferred in some situations (give two reasons).
     
16. 1. There is no algorithm that solves the General Sorting Problem 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.
    
     
17. 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 a bad idea?
     
18. 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?
     

19. 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?
     
20. 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;
    
     

Answers

1. 1. O(n). Linear time.
   2. O(n³). We did not mention a name for this. However, we might call it “cubic time”.
   3. O(n). Linear time.
   4. O(n log n). Log-linear time.
   5. O(n²). Quadratic time.
   6. O(1). Constant time.
2. Generally, the slowest an algorithm can be, and still be considered scalable, is log-linear time, that is, O(n log n). Since the goal is usually to solve large problems, slower algorithms are not really practical.
3. 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.
4. 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.
5. 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.
6. Decrement (--) is not available for some kinds of iterators. Thus, by avoiding using it, we can write code that works on a wider variety of data types.
7. 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.

8. 1. 3n–2 is O(n). Binary Search on an array is O(log n). Multiplying: O(n) × O(log n) = O(n log n).
   2. Summing the numbers is O(n). Finding the product is also O(n). Binary Search is O(log n). Adding, our result is the biggest. Answer: O(n).
9. Divide-and-conquer is an algorithmic strategy. It means to split the input into parts and handle each part separately, often via recursion.
10. 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).
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.

16. 1. There is no algorithm that solves the General Sorting Problem in any time efficiency category faster than O(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, O(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 the General Sorting Problem.
17. Using Quicksort is 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.
18. The Master Theorem only applies when the input is broken into nearly equal-sized parts. Quicksort does not necessarily do this.
19. 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.
20. 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.

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