CSCI 311 Exam 1 Review Questions

• average-case performance
• worst-case performance
• linear running time
• quadratic running time
• cubic running time
• exponential running time
• big-Oh notation
• little-oh notation
• Ω notation
• Θ notation
• recurrence relations
• upper bound
• abstract data type
• recursive divide-and-conquer algorithm
• stable sorting method
• in-place sorting method
• priority queue
• heap
• minimum(maximum) heap property
• heapify

• bubble sort
• insertion sort
• selection sort
• heapsort
• quicksort
• mergesort

3. Write code for:

• heap insert
• heap remove max
• heapify up (see text's Heap-Increase-Key; the relevant code is in the while loop)
• heapify down (see text's Max-Heapify)

4. State definitions for and draw diagrams to illustrate big-Oh notation, Ω notation, and Θ notation.

5. How is algorithm analysis related to CPU speed?

6. What is the height of a complete binary tree with N nodes?

7. A heap with k elements uses locations 1...k of the heap array. True or false? Explain your answer.

8. Given the index of an element in a heap, write a function that changes the value of that element and restores the heap property. Assume that heap functions insert, remove max, heapify up and heapify down are available.

9. How/why is insertion sort used in conjunction with quicksort?

10. Explain median-of-three partitioning, and the two advantages it provides over choosing the last element of the array as the pivot.

11. Show the steps of partitioning the following data using median-of-three partitioning (show each swap):

12. Explain how randomized quicksort works. When is it useful? Under what circumstances might you want to avoid it? Why?

13. Consider quicksort, mergesort, and heapsort. Describe the advantages and disadvantages of each.

14. True/False (explain your answers):

• log n is O(n)
• log n is Θ(n)
• n² + 3n is O(4n²)
• n² + 3n is Θ(4n²)
• 5ⁿ is O(5 log n)
• 5 log n is O(5ⁿ)

15. Determine the running time of the ListPrimes function. (Include time taken by the IsPrime function.)

            bool IsPrime(int x) {

                int k = 2;
                while (k <= SquareRoot(x)) {
                   if (x % k == 0)
                       return false;
                    ++k;
                }
                return true;
            }

            void ListPrimes(int n) {
                int i = 2;
                while (i <= n) {
                    if (IsPrime(i))
                        print i;
                    ++i;
                }
            }
 

16. Determine the running time of the What function. Assume that the sqrt() function runs in constant time.

            int What(int A[], int n) {

                r = sqrt(n);
 
                for (int i = 0; i < r; ++i)
                    for (int j = r+1; j < 2*r; ++j)
                        for (int k = 0; k < n; ++k)
                            A[k] = A[k] + A[i] * A[j];
 
                return A[n-1];
            }
 
17. Suppose Rnd(x) runs in constant time and returns a random integer between 1 and x.
 
The ApproxMin function randomly examines elements of a table and returns the smallest value found.
 
Determine the running time of the ApproxMin function.

            int ApproxMin(int A[], int n) {
                int j = 2 * log(n);
                int min = A[0];
                for (int i = 1; i <= j; ++i) {
                    int k = Rnd(n);
                    if (A[k] < min)
                        min = A[k];
                }
                return min;
            }
 
18. Given an algorithm, derive an expression for its worst-case running time.


19. Given a recursive algorithm, derive the recurrence relation for its running time.


20. Given a recurrence relation, derive an equivalent closed-form expression and prove its correctness.